木琴是一种通过敲击木条来演奏的乐器。单个木条发出的音高总是相同的，因此木琴由不同音高的木条组成。

JOI 君购买了一个由 $N$ 个木条组成的木琴。这些木条排成一排，从左到右编号为 $1$ 到 $N$。编号为 $i$ ($1 \le i \le N$) 的木条发出的音高为 $A_i$ ($1 \le A_i \le N$)。不同的木条发出不同的音高。他知道音高最低的木条的编号小于音高最高的木条的编号。

由于 JOI 君不知道哪个木条发出哪个音高，他打算研究这些木条的音高。

JOI 君有一种独特的听觉；当他同时听到多个声音时，他能分辨出最高音高和最低音高之间的差值。他可以一次敲击一堆木条并听到它们的声音。也就是说，对于整数 $s$ 和 $t$ ($1 \le s \le t \le N$)，他可以同时敲击编号从 $s$ 到 $t$ 的木条，从而获知 $A_s, A_{s+1}, \dots, A_t$ 中的最大值与最小值之差。

他希望在 $10\,000$ 次敲击内确定所有木条的音高。

子任务

所有子任务均满足以下约束：

• $1 \le A_i \le N$ ($1 \le i \le N$)
• $A_i \neq A_j$ ($1 \le i < j \le N$)
• 对于满足 $A_i = 1$ 和 $A_j = N$ 的 $i$ 和 $j$，满足 $i < j$。

共有 3 个子任务。各子任务的分数和约束如下：

实现细节

你需要实现以下函数 solve 来找出木条的音高。

• solve(N)
  • $N$: 木条的数量。
  • 该函数对于每个测试用例仅被调用一次。

你的程序可以调用评测库提供的以下函数：

• query(s, t) 该函数返回指定区间内木条音高的最大值与最小值之差。

  • $s, t$: $s$ 是区间的起始编号，$t$ 是区间的结束编号。即，你敲击编号至少为 $s$ 且至多为 $t$ 的所有木条。
  • 必须满足 $1 \le s \le t \le N$。
  • 调用 query 的次数不能超过 $10\,000$ 次。
  • 如果不满足上述条件，你的程序将被判为 Wrong Answer。

• answer(i, a) 你的程序应使用此函数回答木条的音高。

  • $i, a$: 表示你回答第 $i$ 个木条的音高 $A_i$ 为 $a$。
  • 必须满足 $1 \le i \le N$。
  • 对于同一个 $i$，不能多次调用此函数。
  • 在 solve 函数结束前，必须恰好调用此函数 $N$ 次。
  • 如果不满足上述条件，你的程序将被判为 Wrong Answer。
  • 如果你回答的音高中有与实际不符的，你的程序将被判为 Wrong Answer。

样例

对于 $N = 5, (A_1, A_2, A_3, A_4, A_5) = (2, 1, 5, 3, 4)$ 的通信示例如下：

样例评测程序

样例评测程序按以下格式读取输入：

• 第 1 行: $N$
• 第 $1 + i$ 行 ($1 \le i \le N$): $A_i$

如果你的程序在 solve 结束时正确回答了音高，样例评测程序将打印 Accepted : Q，其中 $Q$ 是调用 query 的次数。 如果你的程序被判为 Wrong Answer，它将打印 Wrong Answer。