//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 fii_lenesi(int poz)
{
      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<<1].suf=arb[poz<<1].pref=arb[poz<<1].best = (1-((int)arb[poz].val_lenes))*(arb[poz<<1].dr-arb[poz<<1].st+1);
      arb[(poz<<1)+1].suf=arb[(poz<<1)+1].pref=arb[(poz<<1)+1].best=(1-((int)arb[poz].val_lenes))*(arb[(poz<<1)+1].dr-arb[(poz<<1)+1].st+1);

      arb[poz].lenes=0;
}

void update_0(int st,int dr,int poz)
{
   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;
   }
   if(arb[poz].lenes)
       fii_lenesi(poz);
   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 update_1(int st,int dr,int poz)
{
   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;
   }
   if(arb[poz].lenes)
       fii_lenesi(poz);

   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].dr<st) || (arb[poz].st>dr))
     return;

   if(arb[poz].st>=st && arb[poz].dr<=dr)
   {
       recompute(aux,aux,arb[poz]);
       return;
   }

   if(arb[poz].lenes)
       fii_lenesi(poz);

   int mijl=(arb[poz].st+arb[poz].dr)>>1;

   if(dr<=mijl)
      query(st,dr,poz<<1);
   else if(st>mijl)
      query(st,dr,(poz<<1)+1);
   else
      query(st,mijl,poz<<1),query(mijl+1,dr,(poz<<1)+1);
}

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