#include "bubblesort2.h"
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int inf=INT_MAX/2;
struct SegTree{
int s;
vi mx,lz;
SegTree(int n){
s=1;
while(s<n)s*=2;
mx.resize(2*s,0),lz.resize(2*s,0);
}
#define ls (p<<1)
#define rs (p<<1|1)
void pushdown(int p){
mx[p]+=lz[p],lz[ls]+=lz[p],lz[rs]+=lz[p];
lz[p]=0;
}
int Q(int p){return mx[p]+lz[p];}
void Add(int b,int e,int v,int l,int r,int i){
if(e<=l||r<=b)return;
if(b<=l&&r<=e){
lz[i]+=v;
return;
}
pushdown(i);
Add(b,e,v,l,(l+r)/2,i*2);
Add(b,e,v,(l+r)/2,r,i*2+1);
mx[i]=max(Q(i*2),Q(i*2+1));
}
void Add(int b,int e,int v){
if(b<e)
Add(b,e,v,0,s,1);
}
};
vi countScans(vi a,vi x,vi v){
int n=a.size(),q=x.size();
vector<pii> lsh;
rep(i,0,n-1)lsh.pb(pii(a[i],i));
rep(i,0,n-1)lsh.pb(pii(v[i],x[i]));
sort(ALL(lsh));
lsh.erase(unique(ALL(lsh)),lsh.end());
int s=lsh.size();
SegTree seg(s);
seg.Add(0,s,-inf);
const auto insert = [&](int p,int r){
int i=lower_bound(ALL(lsh),pii(p,r))-lsh.begin();
seg.Add(i,i+1,inf+r);
seg.Add(i+1,s,-1);
};
const auto erase = [&](int p,int r){
int i=lower_bound(ALL(lsh),pii(p,r))-lsh.begin();
seg.Add(i,i+1,-(inf+r));
seg.Add(i+1,s,1);
};
rep(i,0,n-1)insert(a[i],i);
vi res(q);
rep(i,0,q-1){
erase(a[x[i]],x[i]);
insert(v[i],x[i]);
a[x[i]]=v[i];res[i]=seg.Q(1);
}
return res;
}
