using namespace std;
#include <cstdio>
#include <cmath>
#include <deque>
#define maxn 100000
#define pb push_back
#define pf push_front

deque<int>H[350];
int SQRT;
int n;
int SQRTN;

void insert(int v)
{
  int p=0, i,cnt, n;
  ++SQRTN;
  for(p=0, cnt=512; cnt ; cnt>>=1)
    if(p+cnt<=SQRT)
      if(H[p+cnt].size()==SQRT)
	if(*(H[p+cnt].end()-1)<v)p+=cnt;

  
  //  while(H[p].size()==SQRT && *(H[p].end()-1)<v)++p;
  ++p;
  n=H[p].size();
 
  if(n==0)H[p].pb(v);
  else 
    {
       if(v<H[p][0]) H[p].pf(v);
       else
      	if(v>*(H[p].end()-1)) H[p].pb(v);
	else
	  {
	    
	    //  printf("da\n");
	  for(cnt=512, i=0; cnt ; cnt>>=1)
	    if(i+cnt<n)
	      if(H[p][i+cnt]<=v)i+=cnt;
	  
	  // printf("%d\n", i);
	  H[p].insert(H[p].begin()+i+1, v);
	  }
    }

  int ax;
  while(H[p].size()>SQRT)
    {
      ax=*(H[p].end()-1);
      H[p].pop_back();
      H[++p].pf(ax);
    }
}

void del(int v)
{
  printf("(%d)\n", v);
 int p=0, i,cnt, n;

 for(p=0, cnt=512; cnt ; cnt>>=1)
    if(p+cnt<=SQRT)
      if(H[p+cnt].size()==SQRT)
	if(*(H[p+cnt].end()-1)<=v)p+=cnt;

  
  //  while(H[p].size()==SQRT && *(H[p].end()-1)<v)++p;
 ++p;
  
  // while(H[p].size()==SQRT && *(H[p].end()-1)<v)++p;

  
  n=H[p].size();
 
  for(cnt=512, i=0; cnt ; cnt>>=1)
    if(i+cnt<n)
      if(H[p][i+cnt]<=v)i+=cnt;

  printf("%d %d %d\n",p, i, H[p][i]);
  if(H[p][i]==v)
    {
      --SQRTN;
      if(i==0) H[p].pop_front();
      else if(i==H[p].size()-1) H[p].pop_back();
      else H[p].erase(H[p].begin()+i+1);
    }
  

  int ax;
  while(H[p].size()==SQRT-1)
    {
      ax=*(H[p+1].begin());
      H[p].pb(ax);
      H[p+1].pop_front();
    }


}



int findk(int k)
{
  int P=k/SQRT;
  int Q=k%SQRT;
  
  //printf("%d %d %d\n", P, SQRT, Q);
  ++P; --Q;
  if(Q==-1){--P; Q=SQRT-1;}
  //printf("(%d %d)\n", P, Q);
  if(P<=SQRT)
    if(H[P].size()>=Q+1)return H[P][Q];
    else return 0;

  //  printf("%d %d\n", SQRT, SQRTN);
  //  printf("%d %d\n", P, Q);
  // printf("%d\n", H[P][Q]);

}

void afis()
{
  for(int i=0;i<10;++i)
    if(H[i].size())
    {
      for(int j=0;j<H[i].size();++j)printf("%d ", H[i][j]);
      printf("\n\n\n");
    }


}



int main()
{
  srand(time(0));
   int i;
  n=100000;

  SQRT=(int)sqrt(n)+1;
  
  
  for(i=1;i<=n;++i) insert(rand()%100000000);
  //afis();
    //for(i=1;i<=20;++i) del(findk(1));
  // afis();  
  //  for(i=1;i<=20;++i) printf("%d ", findk(i));
  //printf("\n\n\n");
  //afis();
  return 0;
}