2216 - [Poi2011]Lightning Conductor

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

Input

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

Output

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

Examples

Input

6
5
3
2
4
2
4

Output

2
3
5
3
5
4
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题