[Poi2011]Lightning Conductor

时间限制:25s      空间限制:64MB

题目描述


已知一个长度为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

提示

没有写明提示


题目来源

没有写明来源