Tìm cực tiểu địa phương

Đây là bài toán tương tác.

Hệ thống giữ bí mật một hoán vị $a_1,a_2,\dots ,a_n$ của các số từ $1$ đến $n$. Nhiệm vụ của bạn là tìm một chỉ số $k$ bất kỳ là cực tiểu địa phương.

Chỉ số $i$ ($1\le i\le n$) được gọi là cực tiểu địa phương nếu $a_i<min\{a_{i-1},a_{i+1}\}$, trong đó quy ước $a_0=a_{n+1}=+\infty$. Nói cách khác, hai đầu mút của mảng được coi là lớn hơn mọi phần tử, nên $i=1$ chỉ cần thoả $a_1<a_2$ và $i=n$ chỉ cần thoả $a_n<a_{n-1}$.

Ban đầu bạn chỉ biết giá trị $n$, không biết gì thêm về hoán vị. Mỗi lần hỏi, bạn chọn một chỉ số $i$ và hệ thống cho bạn biết giá trị $a_i$. Bạn được hỏi không quá $100$ câu hỏi.

Một mảng luôn có ít nhất một cực tiểu địa phương, và nếu có nhiều thì in ra chỉ số nào cũng được chấp nhận.

Dữ liệu vào

Đầu tiên hệ thống in ra một dòng chứa số nguyên $n$.

Giao thức tương tác

Sau khi đọc $n$, bạn thực hiện các thao tác sau:

• Để hỏi, in ra một dòng ? i với $1\le i\le n$. Hệ thống trả lời bằng một dòng chứa giá trị $a_i$.
• Khi đã tìm được đáp án, in ra một dòng ! k rồi kết thúc chương trình. Dòng này không tính là một câu hỏi.

Nếu bạn hỏi quá $100$ câu hỏi, hoặc đưa ra chỉ số không phải cực tiểu địa phương, bạn sẽ nhận kết quả sai.

Quan trọng: Sau mỗi lần in ra, bạn phải flush output:

• C++: cout << endl; hoặc cout.flush();
• Python: print(..., flush=True)

Ràng buộc

• $1\le n\le {10}^5$
• $a$ là một hoán vị của $1,2,\dots ,n$

Ví dụ