Progressive climate change has forced the Byteburg authorities to build a huge lightning conductor that would protect all the buildings within the city. These buildings form a row along a single street, and are numbered from $1$ to $n$.

The heights of the buildings and the lightning conductor are non-negative integers. Byteburg's limited funds allow construction of only a single lightning conductor. Moreover, as you would expect, the higher it will be, the more expensive.

The lightning conductor of height p located on the roof of the building $i$ (of height $h_i$) protects the building $j$ (of height hj) if the following inequality holds:

$$ h_j \le h_i + p - \sqrt{\lvert i - j \rvert} $$

where $\lvert i-j \rvert$ denotes the absolute value of the difference between $i$ and $j$.

Byteasar, the mayor of Byteburg, asks your help. Write a program that, for every building i, determines the minimum height of a lightning conductor that would protect all the buildings if it were put on top of the building $i$.

Input Format

In the first line of the standard input there is a single integer $n$ ($1 ≤ n ≤ 500\,000$) that denotes the number of buildings in Byteburg. Each of the following $n$ lines holds a single integer $h_{i}$ ($0 ≤ h_{i} ≤ 1\,000\,000$) that denotes the height of the $i$-th building.

Output Format

Your program should print out exactly $n$ lines to the standard output. The $i$-th line should give a non-negative integer $p_{i}$ denoting the minimum height of the lightning conductor on the $i$-th building.

Example

Input

6
5
3
2
4
2
4

Output

2
3
5
3
5
4