题目背景

译自 COCI 2024/2025 #3 T5。$\texttt{1s,0.5G}$。满分为 $120$。

为了方便测试，公开交互库。

题目描述

这是一道交互题。

有一个初始时为空的数组 $a$。

$n$ 次操作，第 $i$ 次操作向 $a$ 的末尾添加 $x_i$ 个整数。

每次操作后，通过若干次询问，你需要找到最小的未被标记的整数对应的下标 $x$，并给 $a_x$ 打标记。

每次询问，你可以询问两个未被标记的整数 $a_i,a_j$ 的大小关系。

设当前数组长度为 $l$，保证 $\forall 1\le i\lt j\le l$，$a_i\lt a_j$ 和 $a_j\lt a_i$ 恰有一个成立。换句话说，保证数组内元素两两不同。

实现细节

首先读入一个正整数 $n$。接下来依次处理 $n$ 次操作。

对于第 $i$ 次操作，读入一个正整数 $x_i$，表示增加的整数数量。

接下来你可以按照以下格式询问若干次：

• $\texttt{?}$ $i$ $j$：询问 $a_i,a_j$ 的大小关系。
  • 返回 $0$，表示 $a_i\lt a_j$；返回 $1$，表示 $a_i\gt a_j$。
  • 令当前数组长度为 $l$，你需要保证 $1\le i,j\le l$。
  • 你需要保证 $i\neq j$，且 $a_i,a_j$ 未被标记。

按以下格式回答：

• $\texttt{!}$ $x$：当前数组内未被标记的最小整数为 $a_x$。

回答后立刻读入下一个整数 $x_{i+1}$，若这是最后一次操作则立刻结束程序。

在每次询问或者回答后，都要换行并刷新缓冲区。 刷新缓冲区的方式：C++ 中的 std::cout.flush()，std::cout<<std::endl。

输入格式

见【实现细节】。

输出格式

见【实现细节】。

3

3

1

0

0

1

1

1

0

? 1 2

? 1 3

? 2 3

! 2

? 1 4

! 4

? 1 5

! 1

提示

样例解释

样例 $1$ 中，$a=[3,2,4,1,5]$。

• 查询 $a_1$ 与 $a_2$：$a_1\gt a_2$，返回 $1$；
• 查询 $a_1$ 与 $a_3$：$a_1\lt a_3$，返回 $0$；
• 查询 $a_2$ 与 $a_3$：$a_2\lt a_3$，返回 $0$。

不难发现 $a_2$ 为当前未标记的最小值，所以回答 $2$。接下来继续处理剩余的两次操作。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n\le 40$；
• $1\le x_i,\sum x_i\le 2\, 000$。
• 数组内整数两两不同。

计分方式

令你的程序询问次数的最大值为 $q$。

• $q\le 2\, 700$，得 $120$ 分。
• $2\, 700 \lt q\le 7\, 000$，得 $75$ 分。
• $7\, 000 \lt q\le 2\times 10^4$，得 $35$ 分。
• $2\times 10^4 \lt q\le 8\times 10^4$，得 $15$ 分。
• $8\times 10^4\lt q$，得 $0$ 分。