该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

这是一个交互题。

我想和你玩一个游戏……

我们为你隐藏了一个有 $n$ 个顶点的环形图（$3 \le n \le 10^{18}$）。环形图是一个无向图，$n$ 个顶点构成一个环。每个顶点都属于这个环，也就是说环的长度（即其中的边数）恰好为 $n$。环中顶点的顺序是任意的。

你可以通过以下方式进行询问：

• "? a b"，其中 $1 \le a, b \le 10^{18}$ 且 $a \neq b$。对于每次询问，交互器会在单独一行输出从顶点 $a$ 到顶点 $b$ 的两条路径中的一条的长度（随机选取），或者如果 $\max(a, b) > n$，则输出 $-1$。路径的长度指的是路径上的边数。

如果你能在不超过 $50$ 次询问内猜出隐藏图的顶点数（即 $n$），你就获胜了。

注意，交互器的实现保证，对于任意有序对 $(a, b)$，无论你询问多少次 "? a b"，它总是返回相同的值。注意，"? b a" 的答案可能不同。

图中的顶点编号是随机排列的，并且在游戏开始前已经固定。

输入格式

无

输出格式

你最多可以进行 $50$ 次询问。每次询问，输出一行：

• "? a b"，其中 $1 \le a, b \le 10^{18}$ 且 $a \neq b$。交互器会在单独一行输出从顶点 $a$ 到顶点 $b$ 的一条简单路径的长度(不是从 $b$ 到 $a$ 的路径), 或者如果 $\max(a, b) > n$，则输出 $-1$。交互器以等概率选择两条路径中的一条。

如果你的某次询问返回了 $0$，说明你的解已经被判为“答案错误”（例如你询问次数超过 $50$ 次或询问不合法）。此时你的程序应立即终止。否则，在这种情况下你可能会收到“RE”、“TLE”或“WA”的判定。

输出答案时，与询问一样，单独输出一行。输出答案不计入 $50$ 次询问次数。格式如下：

• "! n"：你认为隐藏图的顶点数（$3 \le n \le 10^{18}$）。

注意，交互器的实现保证，对于任意有序对 $(a, b)$，无论你询问多少次 "? a b"，它总是返回相同的值。"? b a" 的答案可能不同。

图中的顶点编号是随机排列的，并且在游戏开始前已经固定。

1

2

-1

? 1 2

? 1 3

? 1 4

! 3

说明/提示

在第一个样例中，图可能如下所示：

在这种情况下，所有顶点对之间的简单路径长度都是 $1$ 或 $2$。

• 第一次询问发现，从顶点 $1$ 到顶点 $2$ 的一条简单路径长度为 $1$。
• 第二次询问发现，从顶点 $1$ 到顶点 $3$ 的一条简单路径长度为 $2$。
• 第三次询问发现，顶点 $4$ 不在图中。因此，图的大小为 $3$。