Description

这是一道交互题。 本题中，交互库是自适应的。

有一个隐藏的 $0\sim n-1$ 的排列 $p_0,p_1,\cdots,p_{n-1}$。

你可以询问至多 $\lceil\frac{5n}{2}\rceil$ 次：每次询问给定 $i,j$（$i\neq j$），交互库会返回 $\gcd(p_{i},p_j)$ 的值。特别地，定义 $\gcd(0,a)=\gcd(a,0)=a$。

找到这个排列中 $1$ 的位置。也就是，找到 $j$，使得 $p_j=1$。

实现细节

本题单个测试点内有多组测试数据。

你不需要，也不应该实现 main 函数。

你需要在文件头加入以下内容：

int ask(int, int);

你应该实现以下的函数：

• int solve(int n)：处理一组排列长度为 $n$ 的数据。
  • 返回一个非负整数 $j$ 满足 $p_j=1$。你需要保证 $0\le j\lt n$，且 $p_j=1$。

实际测评时将会多次调用 solve 函数。

你可以调用以下的函数：

• int ask(int i, int j)：询问 $\gcd(p_i,p_j)$。
  • 你需要保证 $0\le i,j\lt n$，且 $i\neq j$。

需要注意的是，交互库是自适应的，也就是，交互库会根据你的询问（在不矛盾的前提下）动态调整答案。

Input Format

见【实现细节】。

Output Format

见【实现细节】。

1
5

1

2

3

? 1 4

? 1 0

? 2 3

! 3

Hint

样例交互

设原序列为 $[4,2,0,3,1]$。

需要注意的是，样例交互仅为交互格式示意，不代表根据这些信息能唯一确定答案。 交互库是自适应的。

数据范围

• $3\le n,\sum n\le 5\times 10^5$。

再次提醒，交互库是自适应的。