题目背景

特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引用 xylophone.h，而需要把 xylophone.h 中的内容加入文件的开头。即，在程序中 solve 函数的前面加入以下几行语句：

void solve(int N);
int query(int s, int t);
void answer(int i, int a);

题目描述

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

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$ 次敲击之内知道每个木条的音高。

【实现细节】

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

暂不支持 Java 与 Pascal 提交的测评。

提示

【样例交互】

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

【数据范围】

所有子任务满足以下限制：

• $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$​。

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