//Sursa neterminata,plina de greseli caci m-am oprit la mijlocul scrierii ei din motive obiective
#include <iostream>

using namespace std;

struct nod
{
   int st,dr;
   int pref,suf,best;
   bool lenes;
   int val_lenes;
   
   nod()
   {  
      st=0;
      dr=0;
      pref=0;
      suf=0;
      best=0;
      lenes=0;     
      val_lenes=0;
   }    
}arb[262144],aux;
bool v[100005];

void build(int st,int dr,int poz)
{
   arb[poz].st=st;
   arb[poz].dr=dr;
   arb[poz].suf=arb[poz].pref=arb[poz].best=dr-st+1;
   arb[poz].lenes=0;
   arb[poz].val_lenes=0;
   
   if(dr>st)
   {
      int mijl=(st+dr)>>1;      
      build(st,mijl,poz<<1);
      build(mijl+1,dr,(poz<<1)+1);         
   }     
}

int maxim(int a,int b)
{
   if(a>b)
     return a;
   return b;   
}

int maxim(int a,int b,int c)
{
   return maxim(maxim(a,b),c);    
}

void recompute(nod &a,nod b,nod c)
{
   if((b.dr-b.st+1)==b.best)
     a.pref=b.best+c.pref;
   else
     a.pref=b.pref;
   if((c.dr-c.st+1)==c.best)
     a.suf=c.best+b.suf;
   else
     a.pref=c.suf;
   a.best=maxim(b.best,c.best,b.suf+c.pref);  
}

void update_1(int st,int dr,int poz);

void update_0(int st,int dr,int poz)
{     
   if(arb[poz].lenes)
   {   
      arb[poz<<1].lenes=1;
      arb[(poz<<1)+1].lenes=1;
      arb[poz<<1].val_lenes=arb[poz].val_lenes;
      arb[(poz<<1)+1].val_lenes=arb[poz].val_lenes;
      arb[poz].lenes=0;                  
   }
   
   if((arb[poz].dr<st) || (arb[poz].st>dr))
     return;
     
   if(st==dr)
   {
       v[st]=0;
       arb[poz].pref=arb[poz].suf=arb[poz].best=1;
       arb[poz].lenes=0;
       arb[poz].val_lenes=0;
       return;         
   }  
   
   if(arb[poz].st>=st && arb[poz].dr<=dr)
   {
       arb[poz].lenes=1;
       arb[poz].val_lenes=0;               
       arb[poz].pref=arb[poz].suf=arb[poz].best=(arb[poz].dr-arb[poz].st+1)
       return;               
   }
   
   int mijl=(arb[poz].st+arb[poz].dr)>>1;
   
   if(dr<=mijl)
     update_0(st,dr,poz<<1);
   else if(st>mijl)
     update_0(st,dr,(poz<<1)+1);
   else
     update_0(st,mijl,poz<<1),update_0(mijl+1,dr,(poz<<1)+1);
   recompute(arb[poz],arb[poz<<1],arb[(poz<<1)+1]);
}

void leneveste(int poz,bool tip)
{ 
   arb[poz].lenes=1;
   arb[poz].val_lenes=tip;               
   arb[poz].pref=arb[poz].suf=arb[poz].best=((int)tip)(arb[poz].dr-arb[poz].st+1));
}

void update_1(int st,int dr,int poz)
{
   if(arb[poz].lenes)
   {   
      arb[poz<<1].lenes=1;
      arb[(poz<<1)+1].lenes=1;
      arb[poz<<1].val_lenes=arb[poz].val_lenes;
      arb[(poz<<1)+1].val_lenes=arb[poz].val_lenes;
      arb[poz].lenes=0;                  
   }
   
   if((arb[poz].dr<st) || (arb[poz].st>dr))
     return;
   
   if(st==dr)
   {
       v[st]=1;
       arb[poz].pref=arb[poz].suf=arb[poz].best=0;
       arb[poz].lenes=0;
       arb[poz].val_lenes=0;
       return;         
   }     
   
   if(arb[poz].st>=st && arb[poz].dr<=dr)
   {
       arb[poz].lenes=1;
       arb[poz].val_lenes=1;
       arb[poz].pref=arb[poz].suf=arb[poz].best=0;              
       return;               
   }
   
   int mijl=(arb[poz].st+arb[poz].dr)>>1;
   
   if(dr<=mijl)
     update_1(st,dr,poz<<1);
   else if(st>mijl)
     update_1(st,dr,(poz<<1)+1);
   else
     update_1(st,mijl,poz<<1),update_1(mijl+1,dr,(poz<<1)+1);
   recompute(arb[poz],arb[poz<<1],arb[(poz<<1)+1]);
}

void query(int st,int dr,int poz)
{
   if(arb[poz].lenes==1)
   {
      if(arb[poz].val_lenes)
      {
         arb[poz].                   
      }
      else
      {
             
      }                     
   }  
   
   if((arb[poz].dr<st) || (arb[poz].st>dr))
     return; 
   if(st==dr)
   {
       recompute(aux,aux,arb[poz]);      
       return;         
   }    
   
   if(arb[poz].st>=st && arb[poz].dr<=dr)
   {
       arb[poz].lenes=1;
       arb[poz].val_lenes=1;               
       return;               
   }     
   
   
}

int main()
{
    /*
    gol.st=0;
    gol.dr=0;
    plin.st=0;
    plin.dr=0;
    */
    gol.suf=
    system("PAUSE");
    return 0;
}