Watch Towers

You are a builder in the kingdom, and to protect it, the king has ordered to construct $N$ watchtowers each of height $H_i$, where watchtower $i$ is installed at $x = i$.

After constructing the towers, You have realised that there are watchtowers that can’t see other towers because there are other towers blocking the view.

Watchtower $i$ can see watchtower $j$ if you can draw a straight line from tower $i$ to tower $j$ without it intersecting with the body of any other tower (but it can intersect with the top of another tower).

As this kingdom is a magical kingdom, You can use magic to increase the height of any tower you like by an integer $h \geq 0$, but you can only use it once, and because using magic is hard, you want to increase it by the minimum height such that the tower you chose now can see every other tower.

The king is going to do a suprise checkup visit to one of the towers, so you have to determine for each tower $i$ the minimum height $h$ to be increased such that you can see every other tower from the top of it.

It can be proven, that under the given conditions, the answer of each tower is always an integer.

Input

The input file consists of:

• a line containing integer $N$
• a line containing the $N$ integers $H_0, \dots , H_{N−1}$.

Output

The output file must contain a single line consisting of the $N$ integers $D_0, \dots , D_{N−1}$.

Constraints and clarifications

• $1 \leq N \leq 200 \ 000$
• $1 \leq H_i \leq 1 \ 000 \ 000 \ 000$ for each $i = 0 \dots N − 1$

Example 1

stdin

5
4 3 1 3 4

stdout

1 0 1 0 1

Explanation

In the first sample case, tower $i = 1$ cannot see tower $j = 3$ because tower $k = 2$ is blocking the view, so increaseing $i$ by $h = 1$ would make it visible, and same goes for $i = 3$ and $i = 5$.

Example 2

stdin

2
3 7

stdout

0 0

Explanation

In the second sample case, both towers can see eachother, so no need to increase either of them.