Background

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:

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.

Problem Description

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.

Hint

[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.

[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<j\le N)$
• For $i$ and $j$ satisfying $A_i=1,A_j=N$, it holds that $i<j$.

This problem has three subtasks. The scores and additional constraints are shown in the table below:

Translated by ChatGPT 5