JSOI is a small country located in a hilly region. For border defense, the King wishes to build a lighthouse on one of the mountain peaks along the border to illuminate the entire border. The research work for the lighthouse construction has been entrusted to JYY.

JSOI has $N$ consecutive mountain peaks along its border, where the height of the $i$-th peak is $h_i$. For simplicity, we assume these $N$ peaks are arranged in a straight line.

If a lighthouse of height $p$ ($p \ge 0$) is built on the $i$-th peak, JYY has discovered that this lighthouse can illuminate the $j$-th peak if and only if the following inequality is satisfied:

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

The King of JSOI wants JYY to provide the minimum height required for a lighthouse built on each peak such that it can illuminate all other peaks. Can you help JYY?

Input

The input contains a positive integer $N$. The next $N$ lines each contain a positive integer $h_i$, representing the height of the $i$-th peak.

Output

Output $N$ lines, where the $i$-th line contains a non-negative integer representing the minimum height $p_i$ required to build a lighthouse on the $i$-th peak.

Constraints

• For 30% of the data, $N \le 1000$.
• For 60% of the data, $N \le 20000$.
• For 100% of the data, $1 < N \le 10^5$, $0 < h_i \le 10^9$.

Examples

Input 1

6
5
3
2
4
2
4

Output 1

2
3
5
3
5
4