#include "bubblesort2.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <ctime>
using namespace std;
#define pb push_back
#define mp make_pair
int max(int a, int b){ return a>b?a:b;}
const int N=500050;
const int M=2*N;
int ls[M],rs[M],tsz,root,val[M],Max[M],lzy[M],sz[M],y[M];
pair<int,int> id[M];
int MakeNode(pair<int,int> p, int v)
{
tsz++;
val[tsz]=Max[tsz]=v;
id[tsz]=p;
lzy[tsz]=0;
sz[tsz]=1;
y[tsz]=rand();
return tsz;
}
void Push(int c)
{
if(!c || !lzy[c]) return;
if(ls[c]) Max[ls[c]]+=lzy[c],val[ls[c]]+=lzy[c],lzy[ls[c]]+=lzy[c];
if(rs[c]) Max[rs[c]]+=lzy[c],val[rs[c]]+=lzy[c],lzy[rs[c]]+=lzy[c];
lzy[c]=0;
}
void Pull(int c)
{
if(!c) return;
Push(c);
Max[c]=val[c];
sz[c]=sz[ls[c]]+sz[rs[c]]+1;
if(ls[c]) Max[c]=max(Max[c],Max[ls[c]]);
if(rs[c]) Max[c]=max(Max[c],Max[rs[c]]);
}
void Rotate1(int &c)
{
int a=ls[c],b=rs[a];
Push(c);Push(a);
ls[c]=b;
rs[a]=c;
Pull(c);Pull(a);
c=a;
}
void Rotate2(int &c)
{
int a=rs[c],b=ls[a];
Push(c);Push(a);
rs[c]=b;
ls[a]=c;
Pull(c);Pull(a);
c=a;
}
void Del(int &c, pair<int,int> p)
{
if(!c) return;
Push(c);
if(id[c]==p)
{
if(!ls[c]) c=rs[c];
else if(!rs[c]) c=ls[c];
else if(y[ls[c]]>y[rs[c]]) Rotate1(c),Del(rs[c],p);
else Rotate2(c),Del(ls[c],p);
Pull(c);
return;
}
if(id[c]<p) Del(rs[c],p);
else Del(ls[c],p);
Pull(c);
}
void Add(int &c, pair<int,int> p, int x)
{
if(!c){ c=MakeNode(p,x);return;}
Push(c);
if(id[c]<p)
{
Add(rs[c],p,x);
if(y[rs[c]]>y[c]) Rotate2(c);
}
else
{
Add(ls[c],p,x);
if(y[ls[c]]>y[c]) Rotate1(c);
}
Pull(c);
}
void Inc(int &c, pair<int,int> p, int f)
{
if(!c) return;
Push(c);
if(id[c]<p) Inc(rs[c],p,f);
else
{
val[c]+=f;
if(rs[c]) val[rs[c]]+=f,Max[rs[c]]+=f,lzy[rs[c]]+=f;
Inc(ls[c],p,f);
}
Pull(c);
}
int Count(int c, pair<int,int> p)
{
if(!c) return 0;
//printf("(%i %i)\n",id[c].first,id[c].second);
if(id[c]<p)
{
int ans=sz[ls[c]]+1;
ans+=Count(rs[c],p);
return ans;
}
else return Count(ls[c],p);
}
void Print(int c)
{
if(!c) return;
Print(ls[c]);
printf("(%i %i) ",id[c].first,id[c].second);
Print(rs[c]);
}
void Print(){ Print(root);printf("\n");}
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
srand(time(0));
int n,i,q;
for(i=1;i<=tsz;i++) ls[i]=rs[i]=0;
root=tsz=0;
n=a.size();
q=x.size();
vector<pair<int,int> > id;
for(i=0;i<n;i++) id.pb(mp(a[i],i));
sort(id.begin(),id.end());
for(i=0;i<n;i++)
{
int val=id[i].second-i;
//printf("%i\n",val);
Add(root,id[i],val);
}
//Print();
vector<int> ret;
for(i=0;i<q;i++)
{
Del(root,mp(a[x[i]],x[i]));
//Print();
Inc(root,mp(a[x[i]],x[i]),1);
//Print();
//printf("->%i\n",Max[root]);
Inc(root,mp(v[i],x[i]),-1);
//Print();
//printf("->%i\n",Max[root]);
int j=Count(root,mp(v[i],x[i]));
//Print();
Add(root,mp(v[i],x[i]),x[i]-j);
//Print();
//printf("%i<- %i %i\n",x[i]-j,x[i],j);
a[x[i]]=v[i];
ret.pb(Max[root]);
}
return ret;
}
//----------------------//
/*
void Swap(int &a, int &b){ a^=b,b^=a,a^=b;}
int Count(vector<int> a)
{
int sol=0;
bool sw=1;
while(sw)
{
sw=0;
for(int i=0;i+1<a.size();i++) if(a[i]>a[i+1]) Swap(a[i],a[i+1]),sw=1;
if(sw) sol++;
}
return sol;
}
vector<int> Brute(vector<int> a, vector<int> x, vector<int> v)
{
vector<int> ret;
for(int i=0;i<x.size();i++)
{
a[x[i]]=v[i];
ret.pb(Count(a));
}
return ret;
}
void StressTest()
{
srand(time(0));
vector<int> a,x,v;
int c=0;
for(int h=0;h<10000;h++)
{
int n=rand()%10+1,i,q=rand()%5+1;
a.resize(n);x.resize(q);v.resize(q);
for(i=0;i<n;i++) a[i]=rand()%100;
for(i=0;i<q;i++) x[i]=rand()%n,v[i]=rand()%100;
vector<int> sol1=countScans(a,x,v);
vector<int> sol2=Brute(a,x,v);
if(sol1!=sol2)
{
printf("Test case %i:\n",h+1);
printf("%i %i\n",n,q);
for(i=0;i<n;i++) printf("%i ",a[i]);printf("\n");
for(i=0;i<q;i++) printf("%i %i\n",x[i],v[i]);
printf("My sol: ");
for(i=0;i<sol1.size();i++) printf("%i ",sol1[i]);printf("\n");
printf("Brute Force: ");
for(i=0;i<sol2.size();i++) printf("%i ",sol2[i]);printf("\n");
}
else c++;
}
printf("%i of %i is correct!\n",c,10000);
}
int main()
{
StressTest();return 0;
int n,q,i;
vector<int> a,x,v;
scanf("%i %i",&n,&q);
a.resize(n);x.resize(q);v.resize(q);
for(i=0;i<n;i++) scanf("%i",&a[i]);
for(i=0;i<q;i++) scanf("%i %i",&x[i],&v[i]);
vector<int> sol=countScans(a,x,v);
for(i=0;i<sol.size();i++) printf("%i\n",sol[i]);
return 0;
}
*/
//----------------------//
