#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
const int N=5e5+5;
const int INF=1e9;
int n,q,a[N],x[N],v[N];
ii tmp[N+N]; int prv[N+N],nxt[N+N];
void compress(){
rep(i,n) tmp[i]={a[i],i};
rep(i,q) tmp[i+n]={v[i],i+n};
sort(tmp, tmp+n+q);
rep(i,n+q){
if(tmp[i].se<n){
a[tmp[i].se]=i;
} else{
v[tmp[i].se-n]=i;
}
}
rep(i,n+q){
int j=i;
while(j<n+q && tmp[i].fi==tmp[j].fi) ++j;
foru(k,i,j){
prv[k]=i-1;
nxt[k]=j;
}
i=j-1;
}
}
vector<int> Answers;
int mx[N<<3],cnt[N<<3];
int lz[N<<3];
void apply(int id, int val){
mx[id]+=val;
lz[id]+=val;
}
void down(int id){
if(lz[id]==0) return;
apply(id<<1,lz[id]);
apply(id<<1|1,lz[id]);
lz[id]=0;
}
void updP(int x, int val){
int id=1, l=0, r=n+q-1;
while(l<r){
down(id);
int mid=(l+r)>>1;
if(x<=mid){
id=id<<1;
r=mid;
} else{
id=id<<1|1;
l=mid+1;
}
}
if(val==-INF) cnt[id]=0;
else cnt[id]=1;
mx[id]=val;
while(id>1){
id/=2;
mx[id]=max(mx[id<<1], mx[id<<1|1]);
cnt[id]=cnt[id<<1] + cnt[id<<1|1];
}
}
void updR(int u, int v, int val, int id=1, int l=0, int r=n+q-1){
if(u>r||v<l) return;
if(u<=l && r<=v){
apply(id,val);
return;
}
down(id);
int mid=(l+r)>>1;
updR(u,v,val,id<<1,l,mid);
updR(u,v,val,id<<1|1,mid+1,r);
mx[id]=max(mx[id<<1], mx[id<<1|1]);
cnt[id]=cnt[id<<1] + cnt[id<<1|1];
}
int getCnt(int u, int v, int id=1, int l=0, int r=n+q-1){
if(u>r||v<l) return 0;
if(u<=l&&r<=v) return cnt[id];
int mid=(l+r)>>1;
return getCnt(u,v,id<<1,l,mid) + getCnt(u,v,id<<1|1,mid+1,r);
}
void del(int x){
updP(x,-INF);
updR(prv[x]+1, n+q-1, 1);
}
void add(int x, int i){
int cntS=getCnt(0,nxt[x]-1);
updR(prv[x]+1, n+q-1, -1);
updP(x, i-cntS);
}
void mainSolve(){
rep(i,n) add(a[i],i);
rep(i,q){
del(a[x[i]]);
a[x[i]]=v[i];
add(a[x[i]],x[i]);
Answers.eb(mx[1]);
}
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
n=sz(A); q=sz(X);
rep(i,sz(A)) a[i]=A[i];
rep(i,sz(X)) x[i]=X[i], v[i]=V[i];
compress();
mainSolve();
return Answers;
}
