#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
long long n,ma=1e9,inf=1e18;
struct segtree
{
long long l,r,mx,lz;
multiset<long long> ms;
segtree *p[2];
void bd(long long lh,long long rh)
{
long long ii;
l=lh;
r=rh;
mx=-inf;
lz=0;
for(ii=0;ii<2;ii++)
{
p[ii]=0;
}
}
void blc()
{
long long ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
if(!p[ii])
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
p[ii]->mx+=lz;
p[ii]->lz+=lz;
}
lz=0;
}
void ud(long long lh,long long rh,long long w)
{
if(l>rh||r<lh);
else if(l>=lh&&r<=rh)
{
mx+=w;
lz+=w;
}
else
{
long long ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ud(lh,rh,w);
}
mx=max(p[0]->mx,p[1]->mx);
}
}
void ins(long long x,long long w)
{
if(l>x||r<x);
else if(l>=x&&r<=x)
{
ms.insert(w);
mx=*prev(ms.end())+lz;
}
else
{
long long ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ins(x,w);
}
mx=max(p[0]->mx,p[1]->mx);
}
}
void ers(long long x,long long w)
{
if(l>x||r<x);
else if(l>=x&&r<=x)
{
ms.erase(ms.find(w));
if(!ms.empty())
{
mx=*prev(ms.end())+lz;
}
else
{
mx=-inf;
}
}
else
{
long long ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ers(x,w);
}
mx=max(p[0]->mx,p[1]->mx);
}
}
}
sg;
vector<int> countScans(vector<int> a,vector<int> qp,vector<int> qw)
{
long long t=qp.size(),rr,i,k,w;
vector<int> sq;
n=a.size();
sg.bd(1,ma);
for(i=0;i<n;i++)
{
sg.ins(a[i],i+1-n);
sg.ud(1,a[i]-1,1);
}
for(rr=0;rr<t;rr++)
{
k=qp[rr];
w=qw[rr];
sg.ers(a[k],k+1-n);
sg.ud(1,a[k]-1,-1);
a[k]=w;
sg.ins(w,k+1-n);
sg.ud(1,w-1,1);
sq.push_back(sg.mx);
}
return sq;
}
