题目描述

已知一个长度为$\red{n}$的序列$\red{a1,a2,...,an}$。

对于每个$\red{1<=i<=n，}$找到最小的非负整数$\red{p}$满足 对于任意的$\red{j, aj < = ai + p - sqrt(abs(i-j))}$

输入格式

第一行$\red{n，}$$\red{(1<=n<=500000)}$

下面每行一个整数，其中第$\red{i}$行是$\red{ai}$。$\red{(0<=ai<=1000000000)}$

输出格式

$\red{n}$行，第$\red{i}$行表示对于$\red{i，}$得到的$\red{p}$

样例

输入样例

6
5
3
2
4
2
4

输出样例

2
3
5
3
5
4