使用 $O(n\sqrt{n})$做法，自认为没有什么问题，但是T飞了。如果能调过，请收下鄙人的关注。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,K=710;
int n,st[N][20],lg[N]; 
inline int _max(int l,int r){
	if(r<1||l>n)return -(1<<30);
	if(r>n)r=n;
	if(l<1)l=1;
	int w=lg[r-l+1];
	return max(st[l][w],st[r-(1<<w)+1][w]);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>st[i][0];
	for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	for(int i=1;i<20;i++){
		for(int j=1;j<=n-(1<<i)+1;j++)st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
	}
	for(int i=1;i<=n;i++){
		int ret=st[i][0];
		for(int j=1,l1=i,r1,l2,r2=i;j<=K;j++){
			r1=l1-1,l1=i-j*j,l2=r2+1,r2=i+j*j;
			int d1=_max(l1,r1),d2=_max(l2,r2);
			if(d1==-(1<<30)&&d2==-(1<<30))break;
			ret=max(ret,max(d1,d2)+j);
		}
		cout<<ret-st[i][0]<<'\n';
	}
}