Xylophone Query

This is an interactive problem about a xylophone. The xylophone has N wooden bars aligned from left to right (indexed from 1 to N), and each bar i produces a unique pitch A_i (1 ≤ A_i ≤ N). It is known that the bar with the lowest pitch has a smaller index than the bar with the highest pitch.

You have a special auditory sense: when you hear a group of consecutive notes (from index s to t), you can distinguish exactly the difference between the maximum and minimum pitch among these bars. To determine the pitch of each bar, you are allowed to perform at most 10,000 queries of the following type:

For any integers \( s \) and \( t \) (\( 1 \le s \le t \le N \)), by "querying" the interval [s, t], you obtain the value

\( query(s, t) = \max\{A_s, A_{s+1}, \ldots, A_t\} - \min\{A_s, A_{s+1}, \ldots, A_t\} \)

Your task is to determine the pitch A_i for each wooden bar \( 1 \le i \le N \) using these queries.

Implementation Details:

• You must implement a function solve(N) which is called exactly once per test case.
• You can call query(s, t) to obtain the difference between the maximum and minimum pitch in the interval [s, t].
• You are allowed no more than 10,000 queries.
• For each bar i (\(1 \le i \le N\)), you must call answer(i, a) exactly once with the correct pitch \(a\) equal to A_i.

Note: For the purpose of this problem, since we cannot perform interactive queries in our submissions, you will be given the full array as input. Your program should then output the pitches in order. However, your solution should be structured in a way that mimics the interactive version as described.

inputFormat

The input consists of two lines. The first line contains a single integer \(N\) representing the number of wooden bars. The second line contains \(N\) space-separated integers representing the pitches A₁, A₂, ..., A_N.

outputFormat

Output exactly \(N\) lines. The \(i\)-th line should contain the pitch of the \(i\)-th bar.

sample

3
2 1 3

2
1
3