Trò chơi chiếc mũ

Có $n$ học sinh ngồi thành một vòng tròn, đánh số từ $1$ đến $n$ theo chiều vòng tròn, trong đó $n$ là số chẵn. Học sinh $i$ và học sinh $i+1$ ngồi cạnh nhau (với $1\le i\le n-1$), học sinh $n$ và học sinh $1$ cũng ngồi cạnh nhau.

Mỗi học sinh được phát một mảnh giấy ghi một số nguyên. Gọi $a_i$ là số của học sinh $i$. Cách phát thoả mãn: hai học sinh ngồi cạnh nhau luôn có số hơn kém nhau đúng $1$ đơn vị, tức là $|a_i-a_{i+1}|=1$ với mọi $i$ (tính cả cặp $n$ và $1$).

Học sinh $i$ và học sinh $i+\frac{n}{2}$ ngồi đối diện nhau. Hãy tìm một cặp học sinh ngồi đối diện nhau có cùng số, hoặc xác định rằng không tồn tại cặp nào như vậy.

Bạn không được biết trước dãy $a$. Bạn chỉ có thể hỏi giá trị của từng học sinh, và không quá $60$ câu hỏi.

Giao thức tương tác

Đây là bài toán tương tác. Chương trình của bạn giao tiếp với hệ thống chấm qua đầu vào/ra chuẩn.

Đầu tiên, chương trình đọc số nguyên chẵn $n$ là số học sinh.

Sau đó bạn có thể thực hiện hai loại thao tác:

• ? i (với $1\le i\le n$): hỏi số của học sinh $i$. Hệ thống trả lời giá trị $a_i$.
• ! x: đưa ra đáp án và kết thúc chương trình. Nếu tồn tại cặp đối diện có cùng số thì $x$ là chỉ số của một học sinh bất kỳ thuộc một cặp như vậy ($1\le x\le n$); nếu không tồn tại thì $x=-1$.

Số câu hỏi dạng ? không được vượt quá $60$. Thao tác ! x không tính vào giới hạn này. Sau khi in ! x, chương trình phải dừng ngay lập tức.

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

• $2\le n\le 100000$, $n$ chẵn
• $-{10}^9\le a_i\le {10}^9$
• $|a_i-a_{i+1}|=1$ với mọi $i$ (chỉ số tính theo vòng tròn)
• Số câu hỏi tối đa: $60$

Ví dụ