#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
using namespace std ;
const int maxn = 1e6 + 10 , mod = 1e9 + 7 , inf =1e9 ;
vector <int> cm ;
set <int> s[maxn] ;
int seg[4*maxn] , lz[4*maxn] , w[maxn] ;
void shi(int p , int l , int r){
int mid =(l+r)/2 , pl =p<<1 , pr = p<<1|1;
seg[pl] += lz[p] ;
seg[pr] += lz[p] ;
lz[pl] += lz[p] ;
lz[pr] += lz[p] ;
lz[p] = 0;
}
void upd(int le ,int ri , int w, int p =1 , int l = 0 , int r =sz(cm)-1){
int mid = (l+r)/2 ,pl =p<<1 ,pr =p<<1|1 ;
if(le > r || l > ri)return ;
if(le <= l && r <= ri){
seg[p] += w ;
lz[p] += w;
return ;
}
if(l!=r)shi(p,l,r);
upd(le,ri,w,pl,l,mid);
upd(le,ri,w,pr,mid+1,r);
seg[p] = max(seg[pl] , seg[pr]) ;
}
int val(int x){
if(sz(s[x]) == 0)return -inf ;
return (*s[x].rbegin()) ;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
int n = sz(A) , q = sz(X);
rep(i , 0 , n-1){
cm.pb(A[i]) ;
}
rep(i,0,sz(X)-1){
cm.pb(V[i]);
}
sort(all(cm));
cm.resize(unique(all(cm)) - cm.begin()) ;
rep(i , 0, n-1){
A[i] =lower_bound(all(cm) , A[i]) - cm.begin() ;
s[A[i]].insert(i) ;
upd(A[i] , sz(cm)-1 , -1);
}
rep(i , 0 , sz(V)-1){
V[i] = lower_bound(all(cm) , V[i]) - cm.begin();
}
rep(i , 0 , sz(cm)-1){
w[i] = val(i) ;
upd(i , i , w[i]) ;
}
vector <int> res ;
rep(i , 0 , q-1){
int f= A[X[i]];
upd(f , f , -w[f]) ;
upd(V[i] , V[i] , -w[V[i]]);
upd(f , sz(cm)-1 , 1);
s[f].erase(X[i]) ;
s[V[i]].insert(X[i]) ;
w[f] = val(f);
w[V[i]] = val(V[i]) ;
upd(V[i] , V[i] , w[V[i]]) ;
upd(f , f , w[f]);
A[X[i]] =V[i] ;
upd(V[i] , sz(cm)-1 , -1) ;
res.pb(seg[1]+1) ;
}
return res;
}
/*
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
int n , q ;
cin >> n >> q;
vector <int> a ;
rep(i , 1, n){
int x;
cin >> x ;
a.pb(x);
}
vector <int> X , V ;
rep(i , 1, q){
int x, v;
cin >>x>> v ;
X.pb(x);V.pb(v);
}
vector <int> ans = countScans(a,X,V) ;
for(int x : ans){
cout << x << "\n" ;
}
return 0;
}
*/
