#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];
if(!rs[c]) c=ls[c];
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;
if(id[c]<p)
{
int ans=sz[ls[c]]+1;
ans+=Count(rs[c],p);
return ans;
}
else return Count(rs[c],p);
}
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
srand(time(0));
int n,i,q;
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);
}
vector<int> ret;
for(i=0;i<q;i++)
{
Del(root,mp(a[x[i]],x[i]));
Inc(root,mp(a[x[i]],x[i]),1);
Inc(root,mp(v[i],x[i]),-1);
int j=Count(root,mp(v[i],x[i]));
Add(root,mp(v[i],x[i]),x[i]-j);
a[x[i]]=v[i];
ret.pb(Max[root]);
}
return ret;
}
//----------------------//
/*
int main()
{
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;
}
*/
//----------------------//
