题目描述

这是一道交互题。交互库是非自适应的。

有一个隐藏的 $1\sim N$ 的排列 $p_1,\ldots,p_N$。

你可以提问交互库至多 $K$ 次，每次给定 $i,j$（$1\le i\lt j\le N$），交互库会回答 $p_{i},p_{i+1},\ldots,p_{j}$ 中次大元素的下标。

在你提问完后，交互库会向你提问 $Q$ 次，每次给定 $a,b$（$1\le a\lt b\le N$），你需要回答 $p_{a},p_{a+1},\ldots,p_{b}$ 中次大元素的下标。

请注意：在你提问完之后，才能得知交互库的提问。这 $Q$ 次交互库对你的提问一次性给出。

实现细节

首先读入正整数 $N$。

接下来，发起至多 $K$ 次提问：

• $\texttt{?}$ $i$ $j$：提问 $p_{i},p_{i+1},\ldots,p_{j}$ 中次大元素的下标。
  • 你需要保证 $1\le i\lt j\le N$。
• $\texttt{!}$：结束提问。

每次提问后，都需要换行并刷新缓冲区。

在结束提问后，读入正整数 $Q$，以及 $Q$ 对正整数 $a,b$，表示对交互库你的提问。交互库保证 $1\le a\lt b\le N$。

对于每个交互库的提问，输出一行一个正整数，表示次大元素的下标。

在你回答完所有询问后，你需要刷新缓冲区，然后终止程序运行。

交互库是非自适应的。也就是说，询问和排列在交互开始前就已经固定。

输入格式

见「实现细节」。

输出格式

见「实现细节」。

4

2

1

2
1 4
2 3

? 1 2

? 1 3

!



4
2

提示

样例解释

样例的排列为 $p=[2,1,4,3]$。

数据范围

• $N\le 512$；
• $K=Q=2\, 048$。

子任务

子任务 $0$ 为样例。

其中，「$-$」表示「不保证」。

• 特殊性质 $\text{A}$：不存在 $i$ 使得 $p_i\gt \max\{p_{i-1},p_{i+1}\}$。
• 特殊性质 $\text{B}$：$p_1=N$。
• 特殊性质 $\text{C}$：不存在 $i$ 使得 $p_i\lt \min\{p_{i-1},p_{i+1}\}$。

交互库是非自适应的。也就是说，询问和排列在交互开始前就已经固定。