Anna 画了一个正多边形，其 $n$ 个顶点按顺时针方向编号为 $0$ 到 $n-1$。随后，她通过绘制 $n-3$ 条互不相交（除端点外）的对角线将其三角剖分。对角线定义为连接两个不相邻顶点的直线。

首先，定义从顶点 $A$ 到对角线 $D$ 的距离。假设我们从顶点 $A$ 出发，沿顺时针方向移动到下一个顶点，直到到达 $D$ 的其中一个端点。所经过的边数称为 left_distance。类似地，right_distance 是从 $A$ 出发沿逆时针方向移动直到到达 $D$ 的端点所经过的边数。从 $A$ 到 $D$ 的距离定义为 left_distance 和 right_distance 中的最大值。

在示例图片中，从顶点 $0$ 到对角线 $(1,5)$ 的距离为 $2$，其中 left_distance 为 $1$，right_distance 为 $2$。对于对角线 $(0,5)$，从顶点 $0$ 出发的距离为 $5$，其中 left_distance 为 $5$，right_distance 为 $2$。

Anna 想给 Jacob 出一道难题。Jacob 不知道具体画了哪些对角线。他只知道 $n$ 的值，但可以多次询问 Anna 关于某些顶点对的信息，Anna 会告诉他这些顶点之间是否存在对角线。Jacob 的目标是找到距离顶点 $0$ 最近（距离定义如上）的已绘制对角线。你需要通过询问有限次数的问题来帮助他实现目标。

数据范围

• $5 \le n \le 100$

实现细节

你需要在你的提交中实现以下函数：

int solve(int n)

• 该函数会被评测程序调用恰好一次。
• $n$：多边形的顶点数。
• 该函数应返回连接某两个顶点 $a$ 和 $b$ 的对角线，以整数 $a \cdot n + b$ 的形式表示。
• 如果存在多条距离最小的对角线，你可以返回其中任意一条。

上述函数可以调用以下函数：

int query(int x, int y)

• $x$：第一个顶点编号。
• $y$：第二个顶点编号。
• $0 \le x, y \le n-1$
• 如果 $x$ 和 $y$ 之间存在对角线，则返回 $1$，否则返回 $0$。

样例

以下是评测程序的交互示例。该输入对应于上方的图片。 输入仅包含一行，为一个整数：$n$。 样例评测程序会将每次询问输出到标准输出，你需要手动输入 $1$ 或 $0$ 来回答。

样例 1

7

样例 1 交互过程

solve(7)
query(0, 3)
query returns 0
query(0, 5)
query returns 1
query(1, 5)
query returns 1
solve returns 1 * 7 + 5 = 12
Correct!

子任务

设 $q$ 为你在单个测试点中使用的询问次数。此外，令 $w = \frac{n \cdot (n-3)}{2}$。

• 如果你询问了无效问题或猜测错误，该测试点得 $0\%$ 的分数。
• 如果 $q > w$，该测试点得 $0\%$ 的分数。
• 如果 $n < q \le w$，该测试点得 $10 + 60 \cdot \frac{w - q}{w - n} \%$ 的分数。
• 如果 $q \le n$，该测试点得 $100\%$ 的分数。

说明

仅存在一个子任务，你的总分为各测试点得分之和。但在比赛期间，你只能看到一半测试点的得分（价值 $50$ 分）。其余得分将在比赛结束后揭晓。你的最终得分为所有提交中总分的最高值。

Figure 1. 示例图片，展示了从顶点 0 到对角线 (1,5) 的距离计算。