Rabbits Gathering

In a quiet corner of the forest, there is a village inhabited by n rabbits. The i-th rabbit initially stands at position \(p_i\) on the number line. We define the rabbit with a smaller position value as being to the left, and the one with a larger position value as being to the right.

On a moonlit night, all rabbits line up and prepare for a communal hopping activity. According to their custom, each rabbit chooses as its partner the one nearest to it. In case the distance to the rabbit on the left is equal to that on the right, the rabbit chooses the one on the left. Formally, if a rabbit is not at an endpoint, it compares \(p_i - p_{i-1}\) and \(p_{i+1} - p_i\) (using the positions sorted in increasing order) and chooses the one with the smaller distance (choosing the left one in case of a tie). For a rabbit at an endpoint, the only available neighbor is chosen.

After selecting its partner (this choice is fixed and determined by the initial positions), each rabbit hops one unit per move in the direction of its chosen partner. That is, if a rabbit is at position \(x\) and its chosen partner is at a position greater than \(x\) it hops to \(x+1\); otherwise, it hops to \(x-1\).

A special gathering rule applies when two rabbits that are moving toward each other become adjacent (i.e. the distance between them becomes 1). In that case, the left rabbit stays where it is, and the right rabbit makes a hop directly onto the left rabbit's position. With this jump, the pair is considered to have gathered and will stop moving. All other rabbits continue hopping until they have gathered with the pair that originated from the chain of partner selections starting from them.

Ultimately, every rabbit stops moving after it has gathered with the mutual pair (or chain) determined by its fixed partner selections. If two rabbits become mutual partners (i.e. each selects the other) and are at positions \(a\) and \(b\) with \(a < b\), then they will eventually meet at the position \[ F = \left\lfloor\frac{a+b}{2}\right\rfloor, \] where \(\lfloor \cdot \rfloor\) denotes the floor operation. Rabbits that are not initially in a mutual pair follow the chain of choices until they eventually join a group whose meeting point is determined by a mutual pair.

Your task is to determine the final position of each rabbit (in the order of the input) after all rabbits have completed gathering.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of rabbits. The second line contains \(n\) integers \(p_1, p_2, \ldots, p_n\) where \(p_i\) denotes the initial position of the \(i\)-th rabbit (\(0 \le p_i \le 10^9\)). The positions may be given in arbitrary order. Note that when determining directions and neighbor relationships, consider the rabbits sorted by their positions (i.e. the smaller the position, the more to the left).

outputFormat

Output a single line with \(n\) integers. The \(i\)-th integer should be the final position of the \(i\)-th rabbit after all rabbits have gathered.

sample

3
1 3 6

2 2 2