Lightning Conductor Protection

Due to progressive climate change, the Byteburg authorities must build a single lightning conductor to protect all the buildings along a long street. The buildings are numbered from 1 to n and each building i has a height h_i (a non-negative integer). The conductor is to be installed on top of one of the buildings. If a lightning conductor of height p is installed on building j (with height h_j), then it protects building i (with height h_i) if and only if

\(h_j + p \ge h_i + |i - j|\)

This means that the conductor must be tall enough so that, when added to the height of the building it sits on, the sum is at least the height of any other building plus the distance from the conductor’s building. Byteasar, the mayor, requires that for each building (if the conductor were installed on that building) we determine the minimum additional height p such that all buildings are protected.

Note: Since the heights are non-negative integers and the cost increases with the height of the conductor, you should compute the minimal required conductor height for each building.

Mathematically, if the conductor is placed on building j, the minimum required height is

\(p_{j} = \max_{1 \le i \le n} (h_i + |i-j|) - h_j\)

Write a program that, given the number of buildings and their heights, outputs the minimum required conductor height for each building if the conductor were installed on that building.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of buildings. The second line contains n space-separated non-negative integers h₁, h₂, ..., h_n, where h_i is the height of the i-th building.

outputFormat

Output a single line containing n integers. The i-th integer should be the minimum height of the lightning conductor needed if it were placed on building i.

sample

5
5 3 4 1 2

1 3 3 7 7