The Kingdom of Byteland can be seen as a number line. To facilitate communication within the kingdom, the king has designated $n$ elites of the kingdom as messengers. The $i$-th messenger resides at position $p_i$ and can move at a maximum speed of $\frac 12$ units per second in either direction.

Each messenger starts at position $p_i$. A messenger can transmit a message to another messenger instantaneously when they meet at the same position. The king wants to determine, for each messenger $i$ where $1\le i\le n$, the minimum time it will take for all messengers to receive the message if only the $i$-th messenger possesses it initially. Since you are the smartest coder in Byteland, he would like you to answer his question.

Input

The first line contains a positive integer $n$, denoting the number of messengers in Byteland.

The second line contains $n$ integers, the $i$-th being $p_i$, denoting the initial position of the $i$-th messenge, for each $1 \le i \le n$.

Output

Output $n$ integers, the $i$-th being the minimum time it will take for all messengers to receive the message if only the $i$-th messenger possesses it initially. It can be shown that the answer is always an integer.

Constraints

For all all cases, $1\le n\le 2\times 10^5$, $-10^9\le p_i\le 10^9$ for all $1\le i\le n$.

Subtask 1 (3 points): $n=1$.

Subtask 2 (6 points): $n=2$.

Subtask 3 (15 points): $n\le 5$.

Subtask 4 (21 points): $n\le 1000$.

Subtask 5 (26 points): $n$ is even, $p_i=p_{i+1}$ for all odd integers $i$ where $1 \le i \le n$.

Subtask 6 (29 points): No additional constraints.