P15551 Get MiN? Get MeX! 加强版

本题是 [P14134](https://www.luogu.com.cn/problem/P14134) 的加强版，与原题唯一不同在于将询问集合改成了询问区间。 感谢 [cats142857](https://www.luogu.com.cn/user/721928) 老师提供的做法。

**这是一道交互题。** 有一个隐藏的 $0\sim n-1$ 的排列 $a_1, \ldots, a_n$，**这个排列是在你开始询问前就预先确定的，并且这个排列不会随着你的询问而改变**，你可以对这个排列进行若干次询问： - 给定一个区间 $[l,r]$，交互库给出 $\min_{l\le x\le r}a_x+\operatorname*{mex}_{l\le x\le r}a_x$ 的值，此类询问至多使用 $35$ 次。 - 给定一个区间 $[l,r]$，交互库给出 $\min_{l\le x\le r}a_x-\operatorname*{mex}_{l\le x\le r}a_x$ 的值，此类询问至多使用 $1$ 次。 $\operatorname*{mex}_{l\le x\le r}a_x$ 的含义为区间 $[l,r]$ 中最小未出现过的非负整数。 询问之后，你需要计算出排列中 $0$ 的位置。

见【输出格式】。

你需要从**标准输入**读入一个正整数 $n$，表示排列的长度。 对于第一种询问，你需要向**标准输出**输出一个字符 `?`、一个整数 $1$ 以及两个整数 $l,r$，注意此类询问至多使用 $35$ 次。 对于第二种询问，你需要向**标准输出**输出一个字符 `?`、一个整数 $2$ 以及两个整数 $l,r$，注意此类询问至多使用 $1$ 次。 然后你需要清空缓冲区。你可以使用如下语句来清空缓冲区： - C++：`fflush(stdout)`； - Java：`System.out.flush()`； - Python：`stdout.flush()`； - Pascal：`flush(output)`； - 其他语言请参考相关文档。 接下来，你需要从**标准输入**中输入一个整数，代表评测机返回的结果。 询问结束后，你需要先向**标准输出**输出字符 `!`，然后输出一个整数 $p$，表示排列中 $0$ 的位置。输出后，你的程序应立即终止。 如果在某个时刻你的程序读取到 $-10^9$ 作为答案，它应立即退出（例如，通过调用 `exit(0)`）。这种情况下，你将得到“Wrong Answer”，这意味着你提出的问题超过限制或提出了无效问题。如果你忽略这一点，可能会因为程序继续从已关闭的流中读取而得到其他判定结果。

**【样例解释】** **样例仅供展示交互格式，不保证样例输出策略的合理性。** 隐藏的排列为 $a = [5,2,0,1,3,4]$。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | $n \le$ | 特殊性质 | 分值 | |:-:|:-:|:-:|:-:| | $1$ | $1$ | 无 | $1$ | 无 | | $2$ | $2$ | ^ | $2$ | 无 | | $3$ | $36$ | ^ | $10$ | $1,2$ | | $4$ | $10^5$ | 有 | $17$ | 无 | | $5$ | $100$ | 无 | $20$ | $1,2,3$ | | $6$ | $2\times 10^3$ | ^ | $20$ | $1,2,3,6$ | | $7$ | $10^5$ | ^ | $30$ | $1,2,3,4,5,6,7$ | - 特殊性质：保证排列中前 $\lceil \frac{n}{2}\rceil$ 个数为偶数，后 $\lfloor \frac{n}{2}\rfloor$ 个数为奇数。 对于所有数据，保证 $1 \le n \le 10^5$。