CF1479A Searching Local Minimum

这是一个交互题。 Homer 非常喜欢数组，他想和你玩一个游戏。 Homer 从你这里藏起了一个 $a_1, a_2, \dots, a_n$ 的排列，这个排列是 $1$ 到 $n$ 的整数的一个排列。你需要找到任意一个局部极小值的位置 $k$（$1 \leq k \leq n$）。 对于数组 $a_1, a_2, \dots, a_n$，如果某个下标 $i$（$1 \leq i \leq n$）满足 $a_i < \min\{a_{i-1}, a_{i+1}\}$，其中 $a_0 = a_{n+1} = +\infty$，那么称 $i$ 是一个局部极小值的位置。一个数组是 $1$ 到 $n$ 的排列，意味着它包含 $1$ 到 $n$ 的所有整数且每个只出现一次。 一开始，你只知道 $n$ 的值，并不了解这个排列的其它信息。 在每一步交互中，你可以选择任意一个 $i$（$1 \leq i \leq n$）进行一次查询。作为回应，你会得到 $a_i$ 的值。 你需要在最多 $100$ 次查询内，找到任意一个局部极小值的位置 $k$。

你首先读入一个整数 $n$（$1 \leq n \leq 10^5$），单独占一行。 每次你想查询下标 $i$（$1 \leq i \leq n$）时，你需要输出一行 "? $i$"。然后你会读入一行，表示 $a_i$ 的值。总共的 "?" 查询次数不能超过 $100$。 当你找到一个局部极小值的位置 $k$（$1 \leq k \leq n$）时，输出 "! $k$" 并终止你的程序。 如果你的查询格式不合法，或者查询次数超过 $100$，你将会收到 Wrong Answer 的判定。 每次输出查询后，不要忘记输出换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 的判定。具体做法如下： - C++ 使用 fflush(stdout) 或 cout.flush()； - Java 使用 System.out.flush()； - Pascal 使用 flush(output)； - Python 使用 stdout.flush()； - 其它语言请查阅相关文档。 Hack 格式 Hack 的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。 第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）。

见上文输入格式说明。

例如，第一行输入一个整数 $5$，表示数组长度 $n=5$。 示例中进行了五次 "?" 查询，之后我们可以确定数组为 $a=[3,2,1,4,5]$，此时 $k=3$ 是一个局部极小值。 由 ChatGPT 4.1 翻译