题目背景

译自 HIO (COI) 2022 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$		$N \leq 100000$，单词仅由 a 和 b 组成
$4$	$37$	$N \leq 100000$，无额外限制

提示

• 回文的定义为正读和反读相同的字符串。