#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
int n,inf=1e9;
pair<int,int> as[1000069];
struct segtree
{
int l,r,mx,lz;
segtree *p[2];
void bd(int lh,int rh)
{
l=lh;
r=rh;
mx=-inf;
lz=0;
if(l==r);
else
{
int ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
}
}
void blc()
{
int ii;
for(ii=0;ii<2;ii++)
{
p[ii]->mx+=lz;
p[ii]->lz+=lz;
}
lz=0;
}
void ud(int lh,int rh,int w)
{
if(l>rh||r<lh);
else if(l>=lh&&r<=rh)
{
mx+=w;
lz+=w;
}
else
{
int ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ud(lh,rh,w);
}
mx=max(p[0]->mx,p[1]->mx);
}
}
void ins(int x)
{
if(l>x||r<x);
else if(l>=x&&r<=x)
{
mx=lz-(n-1-as[l].sc);
}
else
{
int ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ins(x);
}
mx=max(p[0]->mx,p[1]->mx);
}
}
void ers(int x)
{
if(l>x||r<x);
else if(l>=x&&r<=x)
{
mx=-inf;
}
else
{
int ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ers(x);
}
mx=max(p[0]->mx,p[1]->mx);
}
}
}
sg;
vector<int> countScans(vector<int> a,vector<int> qp,vector<int> qw)
{
int t=qp.size(),rr,i,k,w;
vector<int> sq;
n=a.size();
for(i=0;i<n;i++)
{
as[i]={a[i],i};
}
for(rr=0;rr<t;rr++)
{
k=qp[rr];
w=qw[rr];
as[n+rr]={w,k};
}
sort(as,as+n+t);
sg.bd(0,n+t-1);
for(i=0;i<n;i++)
{
sg.ins(lower_bound(as,as+n+t,mp(a[i],i))-as);
sg.ud(0,lower_bound(as,as+n+t,mp(a[i],0))-as-1,1);
}
for(rr=0;rr<t;rr++)
{
k=qp[rr];
w=qw[rr];
sg.ers(lower_bound(as,as+n+t,mp(a[k],k))-as);
sg.ud(0,lower_bound(as,as+n+t,mp(a[k],0))-as-1,-1);
a[k]=w;
sg.ins(lower_bound(as,as+n+t,mp(w,k))-as);
sg.ud(0,lower_bound(as,as+n+t,mp(w,0))-as-1,1);
sq.push_back(sg.mx);
}
return sq;
}
