Illuminating All Mountains

Consider a sequence of N consecutive mountain peaks with heights \(h_1, h_2, ..., h_N\). For simplicity, assume the mountains lie on a straight line. For the mountain at position \(i\), if a lighthouse of additional height \(p\) (with \(p\ge0\)) is built on top of it, then the lighthouse is said to illuminate the mountain at position \(j\) if and only if

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

The king of JSOI requires that, for every mountain \(i\), one must determine the minimum \(p\) such that a lighthouse built on mountain \(i\) illuminates every other mountain.

Task: For each mountain, compute the minimum additional height \(p_i\) (with \(p_i \ge 0\)) so that for every \(j \neq i\),

\(h_j \le h_i + p_i - \sqrt{|i-j|}\)

This can be rephrased as finding, for every \(i\),

\(p_i = \max\Bigl(0, \max_{j \neq i} \Bigl( h_j - h_i + \sqrt{|i-j|} \Bigr)\Bigr)\)

Output the answer for each mountain in the order from 1 to \(N\) with at least 8 decimal places of precision.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(N\) (the number of mountains).
2. The second line contains \(N\) space-separated integers \(h_1, h_2, \dots, h_N\), representing the heights of the mountains.

outputFormat

Output a single line containing \(N\) real numbers. The \(i\)-th number should represent the minimal additional height \(p_i\) required for the lighthouse on the \(i\)-th mountain, printed with at least 8 decimal places of precision.

sample

3
1 2 3

3.41421356 2.00000000 0.00000000