因为要求P，所以变换一下柿子 ： P≥h[j]-h[i]+sqrt(abs(i-j)); 因求最小，则取等号的值 但暴力去实现是O(n^2)的，1e5的数据跑不过去 考虑优化 可以处理出当前山向前看与向后看的P，取最大的为答案 发现由sqrt(abs(i-j))可以知道j的范围，且枚举sqrt(abs(i-j))为O(sqrt(n))的，可以接受 枚举sqrt(abs(i-j))时，h[i]，sqrt(abs(i-j)) 都知道了，要满足柿子，就要取在能使sqrt(abs(i-j))成立的j的范围中取最大的h[j] 用st表可以O(1)回答范围内的最大值的询问 注意，根号要在运算中是取整的，所以满足的j是有范围的，需要自己去算范围

using namespace std;
const int N=1e5+20;
int h[N], dp[N];
int st[N][20], lg[N], n;
//st表预处理 
void init(){
	for(int i=1;i<=n;i++) lg[i] = lg[i >> 1] + 1, st[i][0] = h[i];
	for(int i=0;i<lg[n];i++){
		for(int j=1;j+(1<<i)<=n;j++){
			st[j][i+1] = max(st[j][i], st[j + (1 << i)][i]);
		}			
	}			
}
int query(int l, int r){//查询 
	l = max(l, 1); r = min(r, n);
	int k = lg[r - l + 1] - 1;
	return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int get(int x){
	return x*x;
}
int main(){
//	freopen("test.in","r",stdin);
//	freopen("ans.out","w",stdout);
	scanf("%d", &n);
	for(int i=1;i<=n;i++){
		scanf("%d", &h[i]);
	}
	init();
//	puts("yes");
	for(int i=1;i<=n;i++){
		int ans=0;
		for(int K=

/*
因为要求P，所以变换一下柿子 ：
		P≥h[j]-h[i]+sqrt(abs(i-j));
因求最小，则取等号的值
但暴力去实现是O(n^2)的，1e5的数据跑不过去
考虑优化
可以处理出当前山向前看与向后看的P，取最大的为答案 
发现由sqrt(abs(i-j))可以知道j的范围，且枚举sqrt(abs(i-j))为O(sqrt(n))的，可以接受
枚举sqrt(abs(i-j))时，h[i],sqrt(abs(i-j)) 都知道了，要满足柿子，就要取在能使sqrt(abs(i-j))成立的j的范围中取最大的h[j]
用st表可以O(1)回答范围内的最大值的询问 
注意，根号要在运算中是取整的，所以满足的j是有范围的，需要自己去算范围 
*/ 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+20;
int h[N],dp[N];
int st[N][20],lg[N],n;
//st表预处理 
void init(){
	for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1,st[i][0]=h[i];
	for(int i=0;i<lg[n];i++){
		for(int j=1;j+(1<<i)<=n;j++){
			st[j][i+1]=max(st[j][i],st[j+(1<<i)][i]);
		}
	}			
}
int query(int l,int r){//查询 
	l=max(l,1);r=min(r,n);
	int k=lg[r-l+1]-1;
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
int get(int x){
	return x*x;
}
int main(){
//	freopen("test.in","r",stdin);
//	freopen("ans.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&h[i]);
	}
	init();
//	puts("yes");
	for(int i=1;i<=n;i++){
		int ans=0;
		for(int K=1;get(K-1)<=i-2;K++){//枚举sqrt(abs(i,j)) 
			int l=i-K*K,r=i-get(K-1)-1;
			ans=max(ans,query(l,r)-h[i]+K);
		}
		for(int K=1;get(K-1)+i<n;K++){
			int l=i+get(K-1)+1,r=i+K*K;
			ans=max(ans,query(l,r)-h[i]+K);
		}
		printf("%d\n",ans);
	}
}