#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define sz(x) (int) (x).size()
#define pii pair<ll,ll>
#define f first
#define s second
const int mxN = 1e6+50;
const int ninf = -1e8;
int cnt;
int st[4*mxN+5];
int laz[4*mxN+5];
void u1(int tl, int tr, int v, int l = 0, int r = cnt-1, int idx = 0){
if (l > tr || r < tl) return;
if (l >= tl && r <= tr){ laz[idx] += v; return; }
int m = (l+r)/2;
u1(tl,tr,v,l,m,2*idx+1);
u1(tl,tr,v,m+1,r,2*idx+2);
st[idx] = max(st[2*idx+1] + laz[2*idx+1], st[2*idx+2] + laz[2*idx+2]);
return;
}
void u2(int t, int v, int l = 0, int r = cnt-1, int idx = 0){
if (l > t || r < t) return;
if (l == r){ st[idx] = v; return;}
// pd(idx);
int m = (l+r)/2;
u2(t,v,l,m,2*idx+1);
u2(t,v,m+1,r,2*idx+2);
st[idx] = max(st[2*idx+1] + laz[2*idx+1], st[2*idx+2] + laz[2*idx+2]);
return;
}
int query(int tl, int tr, int l = 0, int r = cnt-1, int idx = 0){
if (l > tr || r < tl) return ninf;
if (l >= tl && r <= tr) return st[idx] + laz[idx];
int m = (l+r)/2;
return max(query(tl,tr,l,m,2*idx+1), query(tl,tr,m+1,r,2*idx+2)) + laz[idx];
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
ll n = sz(A);
ll q = sz(X);
map<ll,ll> idxs;
vector<ll> all;
/* cout << n << ":\n";
for (int i = 0; i < n; i++) cout << A[i] << " ";
cout << '\n';
cout << q << ":\n";
for (int i = 0; i < q; i++) cout << X[i] << "," << V[i] << " ";
cout << '\n';*/
for (int i = 0; i < n; i++) all.pb((ll)A[i]*n + i);
for (int i = 0; i < q; i++) all.pb((ll)V[i] * n + X[i]);
sort(all.begin(),all.end());
cnt = 0;
ll last = -1;
for (int i = 0; i < sz(all); i++){
if (all[i] == last) continue;
idxs[all[i]] = cnt;
cnt++;
last = all[i];
}
vector<int> res(q);
//for (ll c : all) cout << c << " ";
/// cout << '\n';
//for (pii c : idxs) cout << c.f << ',' << c.s << '\n';
// return res;
for (int i = 0; i < 4*mxN+5; i++) st[i] = ninf;
memset(laz,0,sizeof(laz));
for (int i = 0; i < n; i++) u2(idxs[(ll)A[i]*n+i],i), u1(idxs[(ll)A[i]*n+i]+1, cnt-1,-1);// cout << idxs[(ll)A[i]*n+i] << " ";
//cout << '\n';
ll c;
ll a;
// cout << query(0,cnt-1) << "\n";
for (int i = 0; i < q; i++){
c = idxs[(ll) V[i] * n + X[i]];
a = idxs[(ll) A[X[i]] * n + X[i]];
A[X[i]] = V[i];
u1(a+1,cnt-1,1);
u1(c+1,cnt-1,-1);
u2(a,ninf);
u2(c,X[i]);
// cout << "SWAPPING " << a << ',' << c << "\n";
res[i] = st[0] + laz[0];
// cout << res[i] << " " << st[0] + laz[0] << '\n';
// cout << res[i] << '\n';
// for (int j = 0; j < n; j++) cout << idxs[(ll)A[j] * n + j] << " ";
// cout << '\n';
}
return res;
}
/*
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,q;
cin >> n >> q;
vector<int> A(n);
for (int i = 0; i < n; i++) cin >> A[i];
vector<int> X(q);
vector<int> V(q);
for (int i = 0; i < q; i++) cin >> X[i] >> V[i];
vector<int> res = countScans(A,X,V);
for (int i = 0; i < q; i++) cout << res[i] << "\n";
return 0;
}
*/
