피뢰침

점점 심해지는 기후 변화 때문에 바이트버그(Byteburg) 시는 도시의 모든 건물을 보호할 수 있는 커다란 피뢰침 하나를 세우기로 했다. 건물들은 한 거리를 따라 일렬로 늘어서 있으며, $1$번부터 $n$번까지 번호가 매겨져 있다.

건물의 높이와 피뢰침의 높이는 모두 음이 아닌 정수이다. 예산 문제로 피뢰침은 단 하나만 세울 수 있고, 예상할 수 있듯이 피뢰침이 높을수록 비용이 더 많이 든다.

높이가 $h_i$인 $i$번 건물 위에 세운 높이 $p$의 피뢰침이 높이가 $h_j$인 $j$번 건물을 보호한다는 것은 다음 부등식이 성립함을 뜻한다.

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

여기서 $|i - j|$는 두 건물 번호 차이의 절댓값이다.

모든 건물 $i$에 대하여, $i$번 건물 위에 세웠을 때 도시의 모든 건물을 보호할 수 있는 피뢰침의 최소 높이를 구하라.

첫째 줄에 건물의 개수 $n$ ($1 \le n \le 500{,}000$)이 주어진다.

이어지는 $n$개의 줄에는 각각 $i$번 건물의 높이 $h_i$ ($0 \le h_i \le 1{,}000{,}000$)가 한 줄에 하나씩 주어진다.

정확히 $n$개의 줄을 출력한다. $i$번째 줄에는 $i$번 건물 위에 세워 모든 건물을 보호할 수 있는 피뢰침의 최소 높이 $p_i$(음이 아닌 정수)를 출력한다.