#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define FOR(x,y,z) for(int x=y;x<z;x++)
using namespace std;

struct przedz
{
   int val,s,e;
   przedz(int a, int b, int c){val=a;s=b;e=c;}
   przedz(){}
};
przedz T[1100000];
int N,last;

void update(int pos, int v)
{
   T[pos]=przedz(v,pos-last,pos-last);
   pos/=2;
   while(pos)
   {
      T[pos]=przedz(max(T[pos*2].val,T[pos*2+1].val),T[pos*2].s,max(T[pos*2+1].e,T[pos*2].e));
      pos/=2;
   }
}

int takemax(int x, int p, int q)
{
 //  printf("takemax: %d %d %d\n",x,p,q);
 //  system("pause");
   if(p>q)return 0;
   p=max(p,T[x].s);
   q=min(q,T[x].e);
   if(p==T[x].s && q==T[x].e)return T[x].val;
   return max(takemax(x*2,p,T[x*2].e),takemax(x*2+1,T[x*2].e+1,q));
}

int main()
{
  scanf("%d",&N);
  last=int(pow(2,ceil(log2(N))));
  int a;
  FOR(i,0,N){scanf("%d",&a);update(last+i,a);}
 // FOR(i,1,2*last){if(int(pow(2,ceil(log2(i))))==i)printf("\n");printf("%d %d %d|",T[i].s,T[i].val,T[i].e);}
 /* while(true)
  {
      int y,u;
      scanf("%d %d",&y,&u);
      printf("%d\n",takemax(1,y-1,u-1));
  }*/
  printf("\n");
  FOR(i,0,N)
  {
      int req=T[i+last].val;
      for(int r=0;r*r<i;r++)req=max(req,r+1+takemax(1,max(0,i-(r+1)*(r+1)),i-(r*r)-1));
      for(int r=0;r*r<N-1-i;r++)req=max(req,r+1+takemax(1,i+r*r+1,min(N-1,i+(r+1)*(r+1))));
      printf("%d\n",req-T[i+last].val);
  }
//  system("pause");
  return 0;
}