Lightning Conductor

Worsening climate change has forced the city of Byteburg to build one large lightning conductor that protects every building in the city. The buildings stand in a single row along one street and are numbered from $1$ to $n$.

The heights of the buildings and of the lightning conductor are non-negative integers. The budget allows only a single lightning conductor to be built, and, as you would expect, the taller it is, the more it costs.

A lightning conductor of height $p$ placed on the roof of building $i$ (whose height is $h_i$) protects building $j$ (whose height is $h_j$) exactly when

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

where $|i - j|$ is the absolute difference of the two building numbers.

For every building $i$, determine the smallest height of a lightning conductor that, placed on top of building $i$, would protect all of the buildings.

The first line contains a single integer $n$ ($1 \le n \le 500{,}000$), the number of buildings.

Each of the next $n$ lines contains a single integer $h_i$ ($0 \le h_i \le 1{,}000{,}000$), the height of the $i$-th building.

Print exactly $n$ lines. The $i$-th line must contain one non-negative integer $p_i$: the minimum height of a lightning conductor placed on the $i$-th building that protects every building.