P12202 [COI 2022] 回文子串 / Madioničar

译自 [HIO (COI) 2022](https://hsin.hr/hio2022/zadaci/) T1。

**这是一道交互题**。本题中，交互库是非自适应的。 魔术师 Malnar 需要确定志愿者想象的单词的最长回文子串长度。单词由 $N$ 个小写字母组成，你需要通过以下交互过程推断出最长回文子串的长度 $L$： 1. **提问**：输出 `? l r`，询问区间 $[l, r]$ 的子串是否是回文，程序会返回 $1$（是回文）或 $0$（不是回文），最多允许提问 $200000$ 次。 2. **回答**：确定最长回文子串长度 $L$ 后，输出 `! L` 并结束程序。 ### 交互规则 - 所有输出后需立即刷新缓冲区（例如 Python 使用 `flush=True`）。 - 输入中的 $N$ 表示单词长度，所有区间 $[l, r]$ 需满足 $1 \leq l \leq r \leq N$。

输入仅在第一行包含一个整数 $N$，表示单词长度，后续交互通过提问和回答进行（详见样例）。

- 每行提问格式为 `? l r`。 - 最终答案格式为 `! L`。

### 输入输出样例 **交互过程：** | 程序输出 | 输入（程序回答） | 说明 | |--------------|------------------|----------------------------------------------------------------------| | `? 1 1` | `1` | 询问单字符子串 `n` 是否是回文（是）。 | | `? 2 3` | `0` | 询问子串 `ev` 是否是回文（否）。 | | `? 2 4` | `1` | 询问子串 `eve` 是否是回文（是）。 | | `? 3 5` | `0` | 询问子串 `ven` 是否是回文（否）。 | | `? 1 5` | `1` | 询问整个单词 `neven` 是否是回文（是）。 | | `! 5` | | 确定最长回文子串长度为 5。 | **样例解释：** 志愿者想象的单词为 neven，其最长回文子串为整个字符串，长度为 $5$。 ### 数据规模与约定 对于所有数据，满足 $1 \leq N \leq 100000$。 **子任务及分值**： | 子任务 | 分值 | 限制条件 | |--------|------|-----------------------------------------------| | $1$ | $13$ | $N \leq 7500$ | | $2$ | $25$ | $N \leq 65000$ | | $3$ | $25$ | $N \leq 100000$，单词仅由 `a` 和 `b` 组成 | | $4$ | $37$ | $N \leq 100000$，无额外限制 | ### 提示 - 回文的定义为正读和反读相同的字符串。