#2216. [Poi2011]Lightning Conductor

题目描述

已知一个长度为n的序列a1,a2,...,an。
对于每个1<=i<=n，找到最小的非负整数p满足 对于任意的j, aj < = ai + p - sqrt(abs(i-j))

输入格式

第一行n，(1<=n<=500000)
下面每行一个整数，其中第i行是ai。(0<=ai<=1000000000)

输出格式

n行，第i行表示对于i，得到的p

样例

样例输入

6  

5  

3  

2  

4  

2  

4  

样例输出

2  

3  

5  

3  

5  

4  

数据范围与提示