题目描述

本题是一道交互题（你的程序与评测程序通过标准输入输出进行对话）。

数轴上有点 $1, 2, \ldots, N$，它们按编号从左到右排列（即编号越大，位置越靠右）。

一开始你只知道整数 $N$，并不知道各个点的具体坐标。

之后你可以向评测机提问，最多提问 $\bm{2N}$ 次：

• 选择满足 $1 \le i < j \le N$ 的整数 $i, j$，询问点 $i$ 与点 $j$ 的距离是否不超过 $1$。

请输出距离不超过 $1$ 的点对个数，即满足 $1 \le i < j \le N$ 且点 $i$ 与点 $j$ 距离不超过 $1$ 的整数对 $(i, j)$ 的个数。

交互方式

首先，从标准输入读入表示点数的整数 $N$：

N

接下来，你可以按下面的格式向标准输出提问，最多 $2N$ 次。其中 $i, j$ 必须满足 $1 \le i < j \le N$：

? i j

评测机会从标准输入返回下面两种回答之一：

• Yes：点 $i$ 与点 $j$ 的距离不超过 $1$；
• No：点 $i$ 与点 $j$ 的距离大于 $1$。

当你确定答案 $X$ 后，按下面的格式输出并立即结束程序：

! X

注意事项

• 每次输出后都要换行并 flush 标准输出（C++ 用 endl 或 cout.flush()，否则可能被判 TLE）。
• 交互过程中若输出了不合法的内容，或程序中途异常退出，评测结果不确定。
• 输出答案后请立即结束程序，否则评测结果不确定。
• 点的位置和答案在交互开始时就已经固定，不会随你的提问而改变。

交互示例

下面是 $N = 3$、点 $1, 2, 3$ 的坐标分别为 $0, 0.7, 1.5$ 时的交互过程（坐标不会作为输入给你）：

本次共提问 $3$ 次，不超过 $2N = 6$ 次，且答案正确，因此判定为通过。

约束条件

• $2 \le N \le 10^3$
• $N$ 是整数