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

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

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

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #define ll long long

 #define N 500007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }int n;

 int a[N];

 double f[N],g[N];

 struct data{int l,r,p;}q[N];

 double cal(int j,int i)

 {

     return a[j]+sqrt(abs(i-j))-a[i];

 }

 int find(data t,int x)

 {

     int l=t.l,r=t.r;

     while(l<=r)

     {

         int mid=(l+r)>>;

         if(cal(t.p,mid)>cal(x,mid))

             l=mid+;

         else r=mid-;

     }

     return l;

 }

 void dp(double *F)

 {

     int head=,tail=;

     for(int i=;i<=n;i++)

     {

         q[head].l++;

         if(head<=tail&&q[head].r<q[head].l)head++;

         if(head>tail||cal(i,n)>cal(q[tail].p,n))

         {

             while(head<=tail&&cal(q[tail].p,q[tail].l)<cal(i,q[tail].l))

                 tail--;

             if(head>tail)

                 q[++tail]=(data){i,n,i};

             else

             {

                 int t=find(q[tail],i);

                 q[tail].r=t-;

                 q[++tail]=(data){t,n,i};

             }

         }

         F[i]=cal(q[head].p,i);

     }

 }

 int main()

 {

     n=read();

     for(int i=;i<=n;i++)a[i]=read();

     dp(f);

     for(int i=;i<=n/;i++)swap(a[i],a[n-i+]);

     dp(g);

     for(int i=;i<=n;i++)

         printf("%d\n",max(,(int)ceil(max(f[i],g[n-i+]))));

     return ;

 }