代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 500010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

template<typename T> inline T Max(T a,T b){
    return a>b?a:b;
}

struct node{
    int k,l,r;
    inline node(){}
    inline node(int k,int l,int r) : k(k),l(l),r(r) {}
};
node q[N];

int n,a[N],l,r;
dd f[N],sqr[N];

inline dd calc(int id,int k){
    // printf("id:%d,k:%d\n",id,k);
    // if(id<k) return a[k];
    return (dd)a[k]+sqr[id-k];
}

inline int erfen(int k,int l,int r){
    while(l<r){
        int mid=(l+r)>>1;
        if(calc(mid,q[r].k)>calc(mid,k)) l=mid+1;
        else r=mid;
    }
    return l;
}

inline void insert(int k){
    if(l==r) q[++r]=node(k,1,n);
    int pos;
    while(l<r&&q[r].l>=k&&calc(q[r].l,q[r].k)<calc(q[r].l,k)){
        // printf("1:%lf 2:%lf",calc(q[r].l,q[r].k),calc(q[r].l,k));
        r--;
    }
    if(q[r].r>=k&&calc(q[r].r,q[r].k)>calc(q[r].r,k)){
        if(q[r].r!=n) pos=q[r].r+1;
        else return;
    }
    else pos=erfen(k,Max(q[r].l,k),q[r].r);
    q[r].r=pos-1;q[++r]=node(k,pos,n);
}

inline void solve(int e){
    l=r=0;insert(1);
    for(int i=1;i<=n;i++){
        // if(e==2) printf("q[l+1].r:%d\n",q[l+1].r);
        if(l<r&&q[l+1].r<=i-1) l++;
        else q[l+1].l=i;
        if(l<r){
            int k=q[l+1].k;
            // if(e==2) printf("zhuangyi:i:%d k:%d\n",i,k);
            f[i]=Max(f[i],calc(i,k));
        }
        if(i!=n) insert(i+1);
    }
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    scanf("%d",&n);
    // printf("n:%d\n",n);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]);sqr[i]=sqrt(i);} 
    solve(1);
    // for(int i=1;i<=n;i++) printf("%d\n",(int)ceil(f[i])-a[i]);
    // printf("\n");
    reverse(a+1,a+n+1);reverse(f+1,f+n+1);
    // printf("n:%d\n",n);
    solve(2);
    for(int i=n;i>=1;i--) printf("%d\n",(int)ceil(f[i])-a[i]);
    return 0;
}