Alice 最近收到了一份家庭作业，要求编写一个程序，输出给定排列中任意子数组的逆序对数量。她很开心地完成了作业并获得了满分。下周，他们的家庭作业是找出同一个数组中最长上升子序列的长度。不幸的是，Alice 已经把包含她所需要的排列的那张纸扔掉了。

幸运的是，这个排列存储在她编写的程序中。遗憾的是，她现在只能查询排列中子数组的逆序对数量。由于快要上课了，她请求你帮忙及时解决这个问题。

如果可以通过从数组 $b$ 中删除一些（可能为零）元素得到序列 $a$，则称 $a$ 是 $b$ 的子序列。如果一个序列中每个元素都严格大于其之前的所有元素，则称该序列是上升的。数组的 LLIS 是指其最长上升子序列的长度。

交互

这是一个交互式问题。

交互开始时，先读取一个整数 $n$ ($1 \le n \le 10^3$)，表示排列 $p$ 的长度。

之后，你可以进行最多 $n$ 次查询，格式为 ? l r，其中 $1 \le l \le r \le n$。每次查询应独占一行。每次查询后，读取一个整数，即子数组 $[l, r]$ 中的逆序对数量。逆序对是指满足 $l \le x < y \le r$ 且 $p_x > p_y$ 的整数对 $(x, y)$。

当你确定了 LLIS 后，以 ! ans 的格式输出答案，其中 ans 是 LLIS 的长度。输出答案后，你的程序应立即退出。如果你在输出答案后尝试读取响应，你将收到一个任意判决。

请记住在每次输出查询后刷新缓冲区。

交互器是非自适应的：当交互开始时，排列 $p$ 已经确定。保证从 $1$ 到 $n$ 的每个整数恰好出现一次。

如果交互器收到任何无效或意外的输入，交互器将输出 $-1$ 并立即终止。你的程序应干净地退出以接收 Wrong Answer 判决，否则你收到的判决可能是指示你的提交不正确的任意判决。

如果你的程序在输出答案之前终止，你的提交将收到一个指示你的提交不正确的任意判决。

你将获得一个用于本地测试的命令行工具。该工具顶部有注释说明其用法。

样例

输入样例 1

3
1
1

输出样例 1

? 1 3
? 1 2
! 2