Citizens' safety

[Foamy]

President of Lampville asked you to implement an algorithm which would help him make one of the most dangerous streets in his city safe. To do so, he wants to build a street lantern on one of the buildings on this street. The buildings are standing in a straight line numbered from 1 to x (both x and lantern's height are integers). However, funds are not infinite and therefore they are highly important for the president - the higher the lantern is, the more it will cost. To let the lantern of l height stand on the roof of the q building (of height h_q) so that it will enlight the whole street, for every other r building (of height h_r) such inequality has to apply: h_r<=h_q+l-sqrt(abs(q-r)). You are to deliver an algorithm which would print a minimum height of the lantern on every building such that it would make the street safer.

INPUT: x (1<=x<=500001) meaning how many buildings are there on the street and x times the h_q meaning the height of the q building (0<=h_q<=1 000 000 001).

OUTPUT: x lines and in every line l_q meaning the minimum height of the lantern on q building.

EXAMPLE:
For input:
10
2
9
8
5
6
7
4
3
10
1

The answer is:
11
4
5
8
6
5
8
9
2
11


What I think after thinking for some time is that we should always use the highest building as the h_r in the inequality since if the inequality is true for the highest building, it's automatically true for every other. On the other hand, however, what I wrote above is not always true because we also consider this absolute value of q-r so the height doesn't have the most significance.. Could you please help me with this?

[Foamy]

So maybe I should check for every building and there is no faster way to do this than brute force?