#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7;
int T[LIM], tr[8*LIM], lazy[8*LIM], N=1;
vector<pair<int,int>>skal;
map<pair<int,int>,int>mp;
pair<int,int>pyt[LIM];
void spl(int v) {
tr[2*v]+=lazy[v];
tr[2*v+1]+=lazy[v];
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
if(r<a || l>b) return;
if(a<=l && r<=b) {
tr[v]+=x;
lazy[v]+=x;
return;
}
if(lazy[v]) spl(v);
int mid=(l+r)/2;
upd(2*v, l, mid, a, b, x);
upd(2*v+1, mid+1, r, a, b, x);
tr[v]=max(tr[2*v], tr[2*v+1]);
}
vector<int>countScans(vector<int>A, vector<int>X, vector<int>V) {
int n=A.size(), q=X.size();
rep(i, n) skal.pb({A[i], i});
rep(i, q) skal.pb({V[i], X[i]});
sort(all(skal));
int akt=0;
for(auto i : skal) if(mp.find(i)==mp.end()) mp[i]=akt++;
while(N<akt) N*=2;
rep(i, n) {
int p=mp[{A[i], i}];
upd(1, 0, N-1, p, p, i);
upd(1, 0, N-1, p+1, N-1, -1);
}
vector<int>ans(q);
rep(i, q) {
int p=mp[{A[X[i]], X[i]}];
upd(1, 0, N-1, p, p, -X[i]);
upd(1, 0, N-1, p+1, N-1, 1);
A[X[i]]=V[i];
p=mp[{A[X[i]], X[i]}];
upd(1, 0, N-1, p, p, X[i]);
upd(1, 0, N-1, p+1, N-1, -1);
ans[i]=tr[1];
}
return ans;
}
