CF2087D.Uppercase or Lowercase?

这是一个交互题。

在某个数据库中，存储着 $n$ 个 handle，形式为一个编号列表。你对其中某个特定的 handle $h$ 感兴趣，或者更准确地说，你想知道它在列表中的位置。

你可以向数据库询问列表中的第 $i$ 个位置，数据库会返回该位置上的 handle。

所有 handle 都是非空字符串，由不超过 $20$ 个小写拉丁字母组成，除了第一个字母可以是小写或大写拉丁字母。

你已知所有 handle 都按字典序排序，但问题在于你不知道大写字母是否被认为比小写字母小。换句话说，你不知道是所有以大写字母开头的 handle 排在前面，后面是以小写字母开头的，还是相反，即所有以小写字母开头的 handle 排在前面，后面是以大写字母开头的。

字典序是标准的字符串比较顺序，正式定义如下：

• 如果字符串 $s$ 和 $t$ 在某些位置不同，最早不同的位置为 $i$，那么当且仅当 $s_i < t_i$ 时，字符串 $s$ 在字典序上排在 $t$ 前面（例如，对于字符串 cats 和 current，最早不同的位置是第 $2$ 位，字符 a 小于字符 u，所以 cats 在字典序上小于 current）；
• 如果字符串 $s$ 和 $t$ 没有不同字符的位置，则较短的字符串排在前面。例如，字符串 cat 排在字符串 cats 前面。

由于对数据库的访问受限，你最多只能向数据库询问 $10$ 次。已知你感兴趣的 handle 一定在列表中，请确定它在列表中的位置。

第一行包含整数 $n$ 和字符串 $h$（$1 \le n \le 500$）——列表中 handle 的总数以及你要查找的 handle。

保证所有 handle 都是非空字符串，长度不超过 $20$，只包含小写拉丁字母，除了第一个字母可以是大写字母。

保证所有 handle 已排序、互不相同，且给定的 handle 一定在列表中。

每次询问，输出如下格式的字符串（不含引号）：

• "? i"（$1 \le i \le n$）

评测器会返回一个字符串 $s$，即列表中第 $i$ 个位置上的 handle。

当你准备好输出答案时，输出如下格式的字符串（不含引号）：

• "! i"（$1 \le i \le n$）

并终止程序。输出答案不计入查询次数。

交互器是非自适应的，也就是说，每个测试的 handle 列表在测试开始前就已固定。

如果你的程序询问次数超过 $10$ 次（不包括输出答案）或查询格式不正确，评测器会返回字符串 "-1"。此时你的程序应立即终止，以获得 Wrong Answer 判定。否则，你的解答会继续从已关闭的流中读取，可能会收到任意判定。

每次输出查询后，不要忘记输出换行并刷新输出流。否则，你可能会收到 Idleness limit exceeded 判定。为此，请使用 System.out.flush()。

注意，示例中的空格仅为增强可读性。实际评测时，交互器不会输出任何空行。

由 ChatGPT 4.1 翻译