Số bí mật của Flitwick

Thầy Flitwick đã 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 Flitwick sẽ trả lời:

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

Quy tắc đặc biệt

Tối đa một lời nói dối: Thầy Flitwick được phép nói dối nhiều nhất một lần. Cụ thể:

• Đúng một câu trả lời có thể sai
• Tất cả các câu trả lời còn lại đều đúng

Thầy Flitwick cố định $x$ từ đầu: Khác với một số bài khác, Thầy Flitwick đã quyết định giá trị $x$ trước khi bạn bắt đầu hỏi và không thay đổi.

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 (với $1\le y\le n$)

Để 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}^6$
• Bạn được hỏi tối đa $40$ câu hỏi

Ví dụ

Ghi chú

Trong ví dụ, $x=40$. Thầy Flitwick có thể đã nói dối ở một trong các câu hỏi, nhưng ta vẫn xác định được $x=40$.

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