| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 41 | 11 | 10 | 47.619% |
Initially, Fran has an empty array $a$. Fran processes $n$ queries of the form $x$ — he appends $x$ elements to the end of $a$. After each query, Fran wants to determine the smallest element in the array $a,ドル and once he identifies it, he removes it from the array without altering the indices of the other elements.
Your task is to determine the smallest element of the array for each query by asking questions.
This is an interactive task. Your goal is to write a program that responds to the queries.
The input begins with a single line containing $n$ — the number of queries (1ドル ≤ n ≤ 40$). Then, $n$ queries follow, each starting with $x_i$ — the number of elements added to the array (1ドル ≤ x_i ≤ 2000$).
After each query, your program may ask questions of the form ? $i$ $j$. The interactor will respond with 0ドル$ if $a_i < a_j,ドル or 1ドル$ if $a_i > a_j$. You may assume all elements in the array are distinct. $i \ne j$ must hold, and indices $i$ and $j$ must not correspond to already removed elements.
After determining the smallest element, you must print ! $x,ドル which indicates that $a_x$ is the smallest element in the array $a$ (excluding already removed elements). The index $x$ must not correspond to an already removed element.
You may ask questions multiple times, and after printing the smallest element, the next query begins.
Once you determine the smallest element, the interaction continues with subsequent queries. After the last query, the interaction ends, and your solution is evaluated based on the number of questions asked.
The total length of the array will not exceed 2000ドル$.
Your program will earn points based on the number of questions asked. Let $q$ be the total number of questions your program asked.
3 3 1 0 0 1 1 1 0
? 1 2 ? 1 3 ? 2 3 ! 2 ? 1 4 ! 4 ? 1 5 ! 1
Explanation of the Sample Case:
The final array is of the form 3,ドル 2, 4, 1, 5$.
The first query outputs 1ドル$ because $a_1 > a_2$.
The second query outputs 0ドル$ because $a_1 < a_3$.
The third query outputs 0ドル$ because $a_2 < a_3$.
After this, it can be determined that $a_2$ is the smallest current element, so the output is ! 2ドル$. The interaction continues with the subsequent queries.