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

Một hoán vị $p$ độ dài $n=30000$ được giấu bởi giám khảo. Nhiệm vụ của bạn là tìm chỉ số của giá trị nhỏ nhất trong hoán vị này.

Giám khảo là không thích ứng: hoán vị được chọn trước khi tương tác bắt đầu và không bao giờ thay đổi.

Không giống như các truy vấn so sánh thông thường, giám khảo chỉ so sánh truy vấn hiện tại của bạn với truy vấn trước đó. Cụ thể hơn, nếu truy vấn trước đó của bạn là chỉ số $i$ và bây giờ bạn truy vấn chỉ số $j$, giám khảo cho bạn biết kết quả so sánh giữa $p_i$ và $p_j$.

Bạn có thể thực hiện tối đa $q_{\max}=42000$ truy vấn.

Dữ liệu chấm chính thức gồm 100 tệp kiểm thử riêng biệt. Chương trình của bạn được chạy độc lập trên mỗi tệp.

Giao tiếp

Khi bắt đầu tương tác, chương trình của bạn phải đọc hai số nguyên

$$ n \quad q_{\max}. $$

Đối với các bài kiểm thử chính thức, $n=30000$ và $q_{\max}=42000$.

Để thực hiện một truy vấn, in ra một dòng theo định dạng sau:

$$ \text{? j} $$

với $1 \le j \le n$.

Giám khảo trả lời bằng một ký tự:

• < nếu $p_i < p_j$ với $i$ là chỉ số của truy vấn trước đó (nếu có);
• = nếu đây là truy vấn đầu tiên, hoặc nếu $p_i = p_j$;
• > nếu $p_i > p_j$ với $i$ là chỉ số của truy vấn trước đó (nếu có).

Vì $p$ là một hoán vị, câu trả lời = sau truy vấn đầu tiên chỉ có thể xảy ra nếu bạn truy vấn cùng chỉ số với truy vấn trước đó. Nếu giám khảo trả lời -1, chương trình của bạn phải kết thúc ngay lập tức. Điều này có nghĩa là chương trình của bạn đã vi phạm giao thức tương tác và sẽ nhận được kết quả Sai (Wrong Answer).

Để đưa ra câu trả lời cuối cùng, in ra một dòng theo định dạng sau:

$$ \text{! a} $$

với $a$ là chỉ số mà bạn cho là chứa giá trị nhỏ nhất. Sau khi in câu trả lời, chương trình của bạn phải kết thúc. Câu trả lời cuối cùng không được tính là một truy vấn.

Nếu chương trình của bạn thực hiện nhiều hơn $q_{\max}$ truy vấn, truy vấn một chỉ số không hợp lệ, in một lệnh không hợp lệ hoặc đưa ra câu trả lời cuối cùng sai, nó sẽ nhận kết quả Sai (Wrong Answer).

Sau mỗi truy vấn hoặc câu trả lời được in, hãy xóa bộ đệm (flush) đầu ra. Ví dụ, trong C++ bạn có thể dùng endl hoặc cout.flush().

Ghi chú

Mẫu này chỉ là một ví dụ tương tác và sẽ không xuất hiện trong dữ liệu kiểm thử thực tế. Các dòng có dạng (receiving ... output) là các chỗ giữ chỗ chỉ dùng để căn chỉnh truy vấn và câu trả lời của giám khảo trong mẫu. Trong một bài kiểm thử thực tế, ban giám khảo sẽ không in ra các dòng chỗ giữ chỗ này, và thí sinh không được đọc cũng như in chúng.

Trong ví dụ tương tác này, hoán vị ẩn là $p=(3,1,4,2)$. Các mục bullet dưới đây mô tả tương tác được hiển thị trong mẫu.

• Giám khảo trước tiên gửi $n=4$ và giới hạn truy vấn $5$.
• Truy vấn đầu tiên ? 1 nhận được = vì không có chỉ số nào được truy vấn trước đó.
• Truy vấn ? 2 so sánh $p_1=3$ với $p_2=1$, do đó giám khảo trả lời >.
• Truy vấn ? 4 so sánh $p_2=1$ với $p_4=2$, do đó giám khảo trả lời <. Giá trị nhỏ nhất nằm ở chỉ số $2$, vì vậy ! 2 là đúng.

Công cụ tương tác cục bộ: Tệp attachments/local_interactive.py đính kèm có thể tái tạo cài đặt cục bộ này với --perm 3,1,4,2 --limit 5, nhưng vượt qua được nó không đảm bảo vượt qua được dữ liệu chấm chính thức.