AT_abc466_c.Count Close Pairs

This is an interactive problem (in which your program and the judge program communicate via Standard Input and Output).

On a number line, points $1$, $2$, $\ldots$, $N$ are arranged from left to right in that order.

Initially, you are given only the integer $N$.

Then, you can ask the judge the following question at most $\bm{2N}$ times.

• Choose integers $i$ and $j$ satisfying $1 \leq i < j \leq N$, and ask whether the distance between points $i$ and $j$ is at most $1$.

Output the number of pairs of points whose distance is at most $1$, that is, the number of pairs of integers $(i,j)$ satisfying $1 \leq i < j \leq N$ such that the distance between points $i$ and $j$ is at most $1$.

这是一个交互式问题（即你的程序与评测程序通过标准输入和标准输出进行通信）。

在一条数轴上，点 $1$、$2$、$\ldots$、$N$ 从左到右按此顺序排列。

初始时，你仅被给定整数 $N$。

随后，你最多可向评测程序提出 $\bm{2N}$ 次如下询问：

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

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

Interaction

First, receive the integer $N$ representing the number of points from Standard Input:

$N$

Then, you can repeat the question described in the problem statement to the judge at most $2N$ times.

Output the question to Standard Output in the following format, where $i$ and $j$ must be integers satisfying $1 \leq i<j \leq N$:

? $i$ $j$

As a response to this, one of the following will be given from Standard Input:

Yes

No

Here, Yes indicates that the distance between points $i$ and $j$ is at most $1$, and No indicates that the distance between points $i$ and $j$ is greater than $1$.

Once you have found the answer $X$ to the problem, output your answer in the following format, and then terminate the program immediately:

! $X$### Notes

• Each time you output something, insert a newline at the end and flush Standard Output. Otherwise, the judge result may be TLE.
• The judge result is indeterminate if you output something invalid during the interaction, or if the program terminates prematurely.
• Terminate the program immediately after outputting your answer. Otherwise, the judge result is indeterminate.
• The arrangement of the points and the answer are fixed at the start of the interaction between you and the judge, and do not change depending on, for example, the questions you make.

Constraints

• $2 \leq N \leq 10^3$
• $N$ is an integer.

交互方式

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

$N$

随后，你最多可以向评测程序提出 $2N$ 次本题所述的询问。

请将每次询问按如下格式输出至标准输出，其中 $i$ 和 $j$ 必须为满足 $1 \leq i<j \leq N$ 的整数：

? $i$ $j$

作为回应，标准输入将给出以下两个字符串之一：

Yes

No

其中 Yes 表示点 $i$ 与点 $j$ 之间的距离不超过 $1$；No 表示点 $i$ 与点 $j$ 之间的距离大于 $1$。

当你确定问题的答案 $X$ 后，请按如下格式输出答案，并立即终止程序：

! $X$### 注意事项

• 每次输出后，必须在末尾添加换行符并刷新标准输出缓冲区。否则，评测结果可能为 TLE（超时）。
• 若在交互过程中输出了非法内容，或程序提前终止，则评测结果不确定。
• 输出答案后请立即终止程序。否则，评测结果不确定。
• 点的布局及最终答案在你与评测程序开始交互之初即已固定，不会因你所提出的询问而发生变化。

限制条件

• $2 \leq N \leq 10^3$
• $N$ 为整数。