Problem Description

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

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

The king of JSOI wants JYY to provide, for each peak, the minimum height required to build a lighthouse that can illuminate all other peaks. Can you help JYY?

Input Format

The input contains one line with a positive integer $N$.

In the next $N$ lines, the $i$-th line contains a positive integer $h_i$, representing the height of the $i$-th peak.

Output Format

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.

6
5
3
2
4
2
4

2
3
5
3
5
4

Hint

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

Translated by ChatGPT 5