题目背景

全师避敌。左次无咎，未失常也。

题目描述

题目英文名（子文件夹名）：zou
源代码文件名：zou.cpp
这是一道交互题，不需要文件 IO，使用标准输入输出与交互器进行交互

《三十六计》终于结束了，33DAI 可以逃离这三十六道题目的世界了。

他面前一共有 $n$ 扇门，从左往右排成了一排，每扇门背后都有一个编号。$n$ 扇门背后的编号是 $1\sim n$ 的一个排列（每扇门的编号都是 $1\sim n$ 中的一个且互不相等）。33DAI 不知道每扇门背后的编号是多少。

只有编号为 $n$ 的门是出口，33DAI 可以向 Kitten 发起最多 $20$ 次询问，每次询问格式为 ? l r（$1\le l\lt r\le n$），Kitten 会告诉他从左往右数的第 $l$ 扇门到第 $r$ 扇门中，编号第二大的门是从左往右的第几扇。

如果你已经确定了编号为 $n$ 的门的位置，输出 ! pos（表示你认为编号为 $n$ 的门是从左往右的第 $pos$ 扇门），然后结束程序即可。

交互格式

你的程序会和交互器程序进行标准输入输出的交互。你的可以通过输入得到交互器程序的输出，交互器程序会通过输入得到你的程序的输出。

初始你可以通过输入一个整数，得到 $n$。

紧接着每轮交互你可以输出 ? l r 或者 ! x，然后你需要输出一个换行并刷新缓冲区。

• 如果你输出了 ? l r，你将可以通过输入得到一个 $a$，表示从左往右数的第 $l$ 扇门到第 $r$ 扇门中，编号第二大的门是从左往右的第 $a$ 扇。
• 如果你输出了 ! x，交互器会检查编号为 $n$ 的门是否是从左往右数的第 $x$ 扇，并判断你是否通过了这个测试点。输出这行后，你应该结束程序。

如果你的 ? l r 超过了 $20$ 次，或者 ! x 中的 x 不正确，将无法通过对应的测试点。否则你将通过对应的测试点。

Q：什么是刷新缓冲区？
A：cout<<endl; 可以输出一个换行并刷新缓冲区。你也可以通过执行语句 fflush(stdout); 或者 cout.flush(); 来刷新缓冲区。

样例代码

为了避免你不知道你的程序应该长什么样子，下面给一个能拿到本题 $10$ 分的代码，这个代码中我展示了三种不同的刷新缓冲区的方式，代码思路是先确定编号为 $2$ 的门位置，然后根据前两个数中较小的在哪以及后两个数中较小的在哪儿来找到编号为 $3$ 的门的位置。

你的代码不必像我一样问出所有问题的答案之后再来计算，你可以根据每个问题的答案来决定下一个问题问什么。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    if (n == 3)
    {
        int ans13, ans12, ans23;

        cout << "? 1 3" << endl;
        cin >> ans13; // 显然这会得到编号为 2 的门的位置

        cout << "? 1 2\n";
        cout.flush();
        cin >> ans12;

        cout << "? 2 3\n";
        fflush(stdout);
        cin >> ans23;

        if (ans13 == 1)
        {
            // 此时 2 在第一个位置，看看 3 在后两个位置的哪里即可。
            if (ans23 == 2)
                cout << "! 3" << endl; // 此时编号为 2 1 3
            else
                cout << "! 2" << endl; // 此时编号为 2 3 1
        }
        
        if (ans13 == 2)
        {
            // 此时 2 在第二个位置
            if (ans12 == 1)
                cout << "! 3" << endl; // 此时编号为 1 2 3
            else
                cout << "! 1" << endl; // 此时编号为 3 2 1
        }
        
        if (ans13 == 3)
        {
            // 此时 2 在第三个位置
            if (ans12 == 1)
                cout << "! 2" << endl; // 此时编号为 1 3 2
            else
                cout << "! 1" << endl; // 此时编号为 3 1 2
        }
    }
    return 0;
}

5
5
1
5
5

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

这是一种可能的交互过程，这个例子中有 $5$ 扇门，编号分别为 $3 1 2 5 4$，由此交互器程序给出了每个问题的答案。

• 首先输入一个 5 是门的数量。
• 然后输出了 ? 1 5，询问第一扇门到第五扇门中第二大的是谁，通过输入知道了是第 $5$ 扇。
• 然后输出了 ? 1 4，询问第一扇门到第四扇门中第二大的是谁，通过输入知道了是第 $1$ 扇。
• 然后输出了 ? 2 5，询问第二扇门到第五扇门中第二大的是谁，通过输入知道了是第 $5$ 扇。
• 然后输出了 ? 4 5，询问第四扇门到第五扇门中第二大的是谁，通过输入知道了是第 $5$ 扇。
• 既然通过第一个问题知道了第五扇门是第二大的，通过最后一个问题知道了最后两扇门中第五扇门还是第二大的，因此容易得出结论，第四扇门是最大的。所以输出了 ! 4。

数据规模与约定

对于 $100\%$ 的数据，$2 \le n \le 10^5$。

• 子任务 1（10 分）：保证 $n=3$。
• 子任务 2（20 分）：保证 $n\le 10$ 且编号为 $n-1$ 的门是第一扇门。
• 子任务 3（30 分）：保证 $n\le 10$。
• 子任务 4（40 分）：没有特殊限制。