Problem Description

In a quiet corner of the forest, there is a village where $n$ rabbits live.

On a moonlit night, these rabbits line up in a row and prepare to start a rally jumping activity. Each rabbit occupies a position in the village. For rabbit $i$, its position is $p_i$. We call a smaller position “to the left” and a larger position “to the right”.

According to the village tradition, each rabbit will choose the rabbit closest to itself as its partner and jump in the direction of that partner. If the nearest rabbit on the left and on the right are at the same distance, it will choose the rabbit on the left as its partner.

Each jump of a rabbit can only move one unit to the left or to the right. That is, if a rabbit is currently at position $x$, then after its next jump it will be at $x-1$ or $x+1$.

When the distance between two rabbits moving toward each other becomes $1$, the rabbit on the left will stay where it is, while the rabbit on the right will jump onto the left rabbit’s position, completing the rally.

The rabbits will keep jumping until they complete the rally with the partner they initially chose, and then stop.

After all rabbits have completed the rally, at which position will each rabbit end up?

Input Format

The first line contains an integer $n$, representing the number of rabbits.
The second line contains $n$ integers $p_1,p_2,\cdots,p_n$, separated by single spaces, representing the initial positions of the rabbits.

Output Format

Output one line containing $n$ integers, representing the position of each rabbit after it completes the rally.

5
2 5 7 9 1

1 6 6 6 1

Hint

Sample Explanation

Rabbit $1$ chooses rabbit $5$ as its partner, and rabbit $5$ chooses rabbit $1$ as its partner. Since the distance between them is $1$, rabbit $5$ stays where it is, while rabbit $1$ jumps to position $1$ and completes the rally with rabbit $5$.

Rabbit $2$ chooses rabbit $3$ as its partner, and rabbit $4$ also chooses rabbit $3$ as its partner. For rabbit $3$, rabbits $2$ and $4$ are at the same distance from it, so it chooses the left rabbit $2$ as its partner. Rabbit $2$ jumps one position to the right, rabbit $3$ jumps one position to the left, and rabbit $4$ jumps one position to the left. At this moment, rabbits $2$ and $3$ are both at position $6$, completing the rally (stopping jumping). Rabbit $4$ will continue jumping left until it jumps to position $6$ and completes the rally with rabbit $3$.

Constraints

For $40\%$ of the testdata, $2\le n\le 500$, $1\le p_i\le 10^5$, and $p_1,p_2,\cdots,p_n$ are all distinct.
For all testdata, $2\le n \le 10^5$, $1 \le p_i \le 10^9$, and $p_1,p_2,\cdots,p_n$ are all distinct.

Translated by ChatGPT 5