[IOI2017] The Big Prize
题目背景
这里是洛谷。如果有疑问，可以发帖求助。
如果你习惯于写函数式交互，以下内容可能对你有帮助：
```cpp
vector<int>ask(int i)
{
printf("? %d\n",i);fflush(stdout);
vector<int>ret(2);
scanf("%d%d",&ret[0],&ret[1]);
return ret;
}
int find_best(int n)
{
//
}
main()
{
int n;scanf("%d",&n);
printf("! %d\n",find_best(n));
}
```
无论如何，你都不应引入额外的头文件。
题目描述
“大奖”是一个家喻户晓的 TV 游戏节目。这次你很幸运地进入到最后一轮。已知编号从 $0$ 到 $n-1$ 的 $n$ 个盒子从左到右排成一行，你就站在这排盒子的前面。每个盒子里面放有一个奖品，必须打开盒子才能看到是什么奖品。已知有 $v\leq5$ 种不同类型的奖品。这 $v$ 种类型按照奖品价值的降序从 $1$ 到 $v$ 排列。
类型 $1$ 的奖品是一块钻石，价值最高。所有盒子加起来刚好只有一块钻石。类型 $v$ 的奖品是一块棒棒糖，价值最低。为使得游戏更加激动人心，相对便宜的奖品数量远比价值昂贵的奖品数量要多。更具体一点，对于满足 $2\leq t \leq v$ 的所有 $t$，我们有： 如果类型 $t-1$ 的奖品有 $k$ 个，那么类型 $t$ 的奖品将严格多于 $k^2$ 个。
你的目标是赢得那块钻石。在游戏结束时，你必须打开一个盒子并收取盒子内的奖品。在选择要打开的盒子之前，你可以向节目主持人 Rambod 提一些问题。在每一个问题中，你选择就某个 $i$ 号盒子进行提问。Rambod 将给你一个包含两个整数的数组 $a$ 作为回答。这两个整数的意义如下：
- 在 $i$ 号盒子左面的盒子中，刚好有 $a[0]$ 个盒子中的奖品，价值比 $i$ 号盒子中的奖品价值要高。
- 在 $i$ 号盒子右面的盒子中，刚好有 $a[1]$ 个盒子中的奖品，价值比 $i$ 号盒子中的奖品价值要高。
例如，假设 $n=8$，在你的问题中，你选择就 $i=2$ 号盒子进行提问。Rambod 的回答是 $a=[1,2]$。这个回答的意义是：
- $0$ 号盒子和 $1$ 号盒子中恰好有一个盒子中的奖品比 $i$ 号盒子中的奖品更贵。
- 在 $3,4,\cdots,7$ 号盒子中恰好有 $2$ 个盒子中的奖品比 $2$ 号盒子中的奖品更贵。
你的任务就是通过问少量的问题找出包含钻石的盒子。
输入输出格式
输入格式
你的程序开始运行时，应当读入一个正整数 $n$。
你可以按以下格式发起询问：
- `? i`
意为你选择就 $i$ 号盒子进行提问。你需要保证 $0\leq i<n$。
随后你应当读入两个整数 `a[0] a[1]`，是交互库对你的回答。
你可以按以下格式报告答案：
- `! i`
意为你确定 $i$ 号盒子内有钻石。
随后你应当立刻结束你的程序。
输出格式
在发起询问后，不要忘记刷新缓冲区。你可以使用：
- `fflush(stdout)` or `cout.flush()` in C++;
- `stdout.flush()` in Python;
- 对于其他语言，参阅其文档。
输入输出样例
输入样例 #1
8
0 3
0 1
1 2
0 0
2 1
2 1
1 0
3 0输出样例 #1
? 0
? 1
? 2
? 3
? 4
? 5
? 6
? 7
! 3说明
### 样例解释
```plain
8
3 2 3 1 3 3 2 3
```
上图阐释了这个例子。图中上半部分给出了每个盒子中奖品的类型。图中的下半部分阐释了询问 `? 2`。
### 限制
- $3\leq n \leq200000$.
- 每个盒子中奖品的类型介于 $1$ 和 $v$ 之间（含）。
- 类型 $1$ 的奖品恰有一个。
- 对于所有 $2\leq t \leq v$，如果类型 $t-1$ 的奖品有 $k$ 个，那么类型 $t$ 的奖品将严格多于 $k^2$ 个。
### 子任务与评分
1. （$20$ 分）恰好有 $1$ 个钻石和 $n-1$ 个棒棒糖 （所以，$v=2$）。你可以询问最多 $10000$ 次。
2. （$80$ 分）没有附加限制。
在子任务 2 中你可以获得部分分。令 $q$ 是在这个子任务的所有测试数据上发起询问的最大次数，那么你在这个子任务上的得分将按照下表计算：
