该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

#5707. 「COCI 2024/2025 #3」Procesor

标签: 交互 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #3 T5「Procesor」

起初，Fran 拥有一个空数组 $a$。Fran 总共处理 $n$ 个询问，每个询问的形式为 $x$，即他将 $x$ 个元素追加到数组 $a$ 的末尾。在每次询问后，Fran 都想确定数组 $a$ 中的最小值，一旦确定，他就会将其从数组中移除，且不改变其他元素的编号。

你的任务是通过询问来确定每次询问后数组中的最小值。

交互方式

这是一道交互题。你的目标是编写一个程序来响应这些询问。

输入首先包含一行，包含 $n$ $(1 \leq n \leq 40)$，表示询问的数量。随后是 $n$ 个询问，每个询问以 $x_{i}$ 开头 ——即添加到数组中的元素数量 $(1 \leq x_{i} \leq 2000)$。

在每次询问后，你的程序可以给出形式为 ? i j 的询问。交互器将返回 $0$（如果 $a_{i} < a_{j}$）或 $1$（如果 $a_{i} > a_{j}$）。你可以假设数组中的所有元素均不相同。且必须满足 $i \neq j$，且编号 $i$ 和 $j$ 不能对应已经移除的元素。

在确定最小值后，你必须输出 ! x，这表示 $a_{x}$ 是数组 $a$ 中当前最小的元素（排除已移除的元素）。编号 $x$ 不能对应已经移除的元素。

你可以多次提问，输出最小值后，下一次询问开始。

当你确定最小值后，交互将继续进行后续的询问。在最后一次询问结束后，交互结束，你的方案将根据所提出的问题数量进行评分。

数组的总长度不会超过 $2000$。

评分

你的程序将根据所提出的问题数量获得分数。设 $q$ 为你的程序提出的问题总数。

• 如果 $q \leq 2700$，你的程序将获得 $120$ 分。
• 如果 $2700 < q \leq 7000$，你的程序将获得 $75$ 分。
• 如果 $7000 < q \leq 2 \cdot 10^{4}$，你的程序将获得 $35$ 分。
• 如果 $2 \cdot 10^{4} < q \leq 8 \cdot 10^{4}$，你的程序将获得 $15$ 分。

样例

输入

3
3

1

0

0

1

1

1

0

输出

? 1 2

? 1 3

? 2 3

! 2

? 1 4

! 4

? 1 5

! 1

最终数组的形式为 $3, 2, 4, 1, 5$。

第一个询问输出 $1$ 因为 $a_{1} > a_{2}$。

第二个询问输出 $0$ 因为 $a_{1} < a_{3}$。

第三个询问输出 $0$ 因为 $a_{2} < a_{3}$。

在此之后，可以确定 $a_{2}$ 是当前最小的元素，因此输出 ! 2。交互继续进行后续询问。