你可能听说过，Malnar 先生在业余时间会表演魔术。他最近在著名的电视节目 Penn & Teller: Fool Us 中的亮相风靡全球。他自称为“魔术师 Malnar 先生”（The Magical Mr. Malnar），表演了一个令人难以置信的心灵感应魔术，让所有人为之倾倒。

他首先从观众中邀请了一位热心的志愿者，并请其在脑海中构思一个由恰好 $N$ 个字母组成的任意字符串。接着，他开始娱乐观众，期间偶尔瞥一眼志愿者，最后他宣称：“你的字符串中最长回文子串的长度为 $L$”。在志愿者确认这确实正确后，观众们都惊呆了。

然而，细心的观众和 Malnar 先生的密友怀疑这并不是读心术，而是通过巧妙的措辞选择，结合对面部表情的极佳解读，从而获取了足够的信息来完成这个魔术。

虽然看起来 Malnar 先生只是在开玩笑，但他时不时会提到某个数字区间 $[l, r]$（其中 $1 \le l \le r \le N$），并短暂地看一眼志愿者。有传言说，他仅凭志愿者的面部表情，就能确定该字符串中从第 $l$ 个字母到第 $r$ 个字母（闭区间）组成的子串是否为回文。

你需要编写一个程序，以证实如果传言属实，Malnar 先生确实能够收集到足够的信息，来确定志愿者所选择的秘密字符串的最长回文子串的长度。

（注：回文是指正着读和倒着读都相同的字符串。字符串的子串是指由该字符串中第 $l$ 个到第 $r$ 个字符组成的字符串，其中 $1 \le l \le r \le N$。回文子串是指同时也是回文的子串。）

交互

这是一个交互式任务。你的程序必须与主办方编写的程序进行通信，该程序模拟了题目描述中志愿者的行为。

在交互开始前，你的程序应当从标准输入中读取一个整数 $N$，即秘密字符串的长度。

之后，你的程序可以通过向标准输出写入来发送查询请求。每个查询必须单起一行，格式为 ? l r，其中 $1 \le l \le r \le N$。在写入每个查询后，你的程序应当刷新输出缓冲区（flush），并从标准输入中读取答案。如果子串 $[l, r]$ 是回文，则答案为 1；如果不是，则答案为 0。你的程序最多可以进行 $200\,000$ 次此类查询。

在你的程序推导出最长回文子串的长度后，应当向标准输出写入一行，格式为 ! L，其中 $L$ 为该长度。之后，你的程序应当再次刷新输出缓冲区，并正常结束运行。

注意：你可以从评测系统中下载示例源代码，其中展示了如何正确进行交互（包括刷新输出缓冲区）。

数据范围

样例

输入样例 1

5
1
0
1
0
1

输出样例 1

? 1 1
? 2 3
? 2 4
? 3 5
? 1 5
! 5

说明 1

在这个例子中，志愿者选择的字符串是 neven。

• 首先，程序从标准输入读取字符串长度 $N = 5$。
• 程序询问 ? 1 1，系统回答 1（子串 n 是回文）。
• 程序询问 ? 2 3，系统回答 0（子串 ev 不是回文）。
• 程序询问 ? 2 4，系统回答 1（子串 eve 是回文）。
• 程序询问 ? 3 5，系统回答 0（子串 ven 不是回文）。
• 程序询问 ? 1 5，系统回答 1（子串 neven 是回文）。
• 最后，程序确定最长回文子串的长度为 $5$，输出 ! 5 并结束。