题目描述

译自 JOI Open 2018 T4 「木琴 / Xylophone」

木琴是一种乐器，人可以通过敲击木条来演奏它。单个木条总是发出同样音高的音，因此一个木琴包含不同种音高的木条。

JOI 君买了一个有 $N$ 个木条的木琴。这 $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},\ldots ,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$​。

本题有三个子任务。子任务分值及附加限制如下表所示：

实现细节

你需要实现函数 $\texttt{solve}$ 以求出每个木条的音高。

• $\texttt{solve(N)}$

  • $\texttt{N}$：木条的数量。
  • 这个函数每个测试点调用恰好一次。

你的程序可以调用评分器实现的如下函数。

• $\texttt{query(s, t)}$

  这个函数返回在给定区间中木条音高最大值与最小值的差。

  • $\texttt{s, t}$：$s$ 是要敲击的木条区间中第一个数，$t$ 是最后一个数。也就是说，你需要敲击编号在 $[s,t]$ 区间内的所有木条。
  • 必须保证 $1\le s\le t\le N$。
  • 你不能调用 $\texttt{query}$ 函数超过 $10\ 000$ 次。
  • 如果上述条件不满足，你的程序会被判为 Wrong Answer。

• $\texttt{answer(i, a)}$

  你的程序应当用这个函数回答每个木条的音高。

  • $\texttt{i, a}$：这意味着你回答了 $A_i$ 的值为 $a$，其中 $A_i$ 指木条 $i$ 的音高。
  • 必须保证 $1\le i\le N$。
  • 你不能对于相同的 $\texttt i$ 调用超过一次这个函数。
  • 你必须在函数 $\texttt{solve}$​ 结束前调用恰好 $N$ 次此函数。
  • 如果上述条件不满足，你的程序会被判为 Wrong Answer。
  • 如果你的回答与实际音高有不同，你的程序会被判为 Wrong Answer。

C++ 的提交须引入 $\texttt{xylophone.h}$ 库，暂不支持 Java 与 Pascal 提交的测评。

样例交互

一个对于 $N=5,(A_1,A_2,A_3,A_4,A_5)=(2,1,5,3,4)$ 的样例交互过程如下。

样例交互器

样例交互器按如下格式读取输入：

第一行一个整数 $N$。

接下来 $N$ 行，每行一个整数 $A_i$。

如果你的程序在 $\texttt{solve}$ 函数结束时回答音高正确，样例交互器会输出 $\texttt{Accepted : Q}$，其中 $Q$ 为 $\texttt{query}$ 函数的调用次数。

如果你的程序被判为 Wrong Answer，则输出 $\texttt{Wrong Answer}$。