Số bí mật của Dumbledore

Thầy Dumbledore đã chọn một số nguyên bí mật $x$ trong khoảng từ $1$ đến $n$.

Bạn có thể đặt câu hỏi theo định dạng:

? y

Thầy Dumbledore sẽ trả lời:

• YES nếu $x\le y$
• NO nếu $x>y$

Sau khi tìm ra đáp án, in ra:

! x

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$.

Dữ liệu ra

Để hỏi: ? y

Để trả lời: ! x

Sau mỗi truy vấn, bạn phải flush output.

Ràng buộc

• $1\le n\le {10}^9$
• Bạn được hỏi tối đa $30$ câu hỏi

Ví dụ

Ghi chú

Trong ví dụ, $x=7$:

• $7>5$ nên trả lời NO
• $7\le 8$ nên trả lời YES
• $7>6$ nên trả lời NO
• $7\le 7$ nên trả lời YES → tìm được đáp án

Tham khảo: Hướng dẫn giải bài tập Interactive