P9599 [JOI Open 2018] Xylophone / Xylophone

**Special reminder: Due to Luogu’s special interactive mechanism, you cannot include `xylophone.h` in your program. Instead, you need to paste the contents of `xylophone.h` at the beginning of your file. That is, add the following lines before the `solve` function in your program:** ```cpp void solve(int N); int query(int s, int t); void answer(int i, int a); ``` **Also, it is not recommended to submit this problem using C++14 (GCC 9). It is recommended to use C++17 or a newer language version.**

A xylophone is a musical instrument. People can play it by striking wooden bars. Each single bar always produces a sound of the same pitch, so a xylophone contains bars with different pitches. JOI has bought a xylophone with $N$ bars. These $N$ bars are arranged in a line and numbered from $1$ to $N$ from left to right. The bar numbered $i\ (1\le i\le N)$ can produce a sound with pitch $A_i\ (1\le A_i\le N)$. Different bars produce different pitches. He knows that the bar with the lowest pitch has a smaller index than the bar with the highest pitch. Since JOI does not know the pitch of each bar, he decides to study the pitches of these bars. JOI has a unique sense of pitch. When he hears several sounds in a row, he can tell the difference between the highest and the lowest pitch. He can strike some consecutive bars once and listen to their sounds. In other words, for two integers $s$ and $t\ (1\le s\le t\le N)$, he can strike the bars numbered from $s$ to $t$ in order, to learn the difference between the maximum and minimum values among $A_s,A_{s+1},\ldots ,A_t$. He wants to determine the pitch of every bar within $10\ 000$ strikes. --- **[Implementation Details]** You need to implement the function `solve` to determine the pitch of every bar. - `solve(N)` - $N$: the number of bars. - This function is called exactly once for each test case. Your program may call the following functions implemented by the grader. - `query(s, t)` This function returns the difference between the maximum and minimum pitches among the bars in the given interval. - $s, t$: $s$ is the first bar in the interval to strike, and $t$ is the last. That is, you need to strike all bars with indices in $[s,t]$. - You must ensure $1\le s\le t\le N$. - You may not call `query` more than $10\ 000$ times. - If any of the above conditions is not satisfied, your program will be judged **Wrong Answer**. - `answer(i, a)` Your program should use this function to output the pitch of each bar. - $i, a$: this means you claim that $A_i$ equals $a$, where $A_i$ is the pitch of bar $i$. - You must ensure $1\le i\le N$. - You may not call this function more than once for the same $\texttt i$. - You must call this function exactly $N$ times before the function $\texttt{solve}$ ends. - If any of the above conditions is not satisfied, your program will be judged **Wrong Answer**. - If your answer differs from the actual pitches, your program will be judged **Wrong Answer**. Submissions in Java and Pascal are not supported for this problem.

N/A

N/A

**[Sample Interaction]** A sample interaction for $N=5,(A_1,A_2,A_3,A_4,A_5)=(2,1,5,3,4)$ is as follows. | Call | Return Value | | :---------------------: | :----------: | | $\texttt{query(1, 5)}$ | | | | $4$ | | $\texttt{answer(1, 2)}$ | | | $\texttt{query(3, 5)}$ | | | | $2$ | | $\texttt{answer(2, 1)}$​ | | | $\texttt{answer(3, 5)}$​ | | | $\texttt{answer(5, 4)}$​ | | | $\texttt{answer(4, 3)}$​ | | **[Constraints]** All subtasks satisfy the following constraints: - $1\le A_i\le N\ (1\le i\le N)$ - $A_i\neq A_j\ (1\le i