시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB41111047.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.

  • If $q ≤ 2700$, your program will earn $120$ points.
  • If $2700 < q ≤ 7000$, your program will earn $75$ points.
  • If $7000 < q ≤ 2 \cdot 10^4$, your program will earn $35$ points.
  • If $2 · 10^4 < q ≤ 8 \cdot 10^4$, your program will earn $15$ points.

예제 입력 1

3
3

1

0

0

1

1

1

0

예제 출력 1



? 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.

채점 및 기타 정보

  • 120점 이상을 획득해야 를 받는다.
  • 예제는 채점하지 않는다.