题目描述

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

实现细节

你需要实现函数 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$。

• 你不能对于相同的 i 调用超过一次这个函数。

• 你必须在函数 solve 结束前调用恰好 $N$ 次此函数。

• 如果上述条件不满足，你的程序会被判为 Wrong Answer。

• 如果你的回答与实际音高有不同，你的程序会被判为 Wrong Answer。

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

输入格式

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

第一行一个整数 $N$

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

输出格式

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

如果你的程序被判为 Wrong Answer，则输出 Wrong Answer。

5
2
1
5
3
4

样例交互

数据规模与约定

$2\le N\le 5\ 000$