#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=500007,pot=1<<20;
map<int,int>id[N];
int lzy[2*pot+7];
int seg[2*pot+7];
void push(int v)
{
lzy[2*v]+=lzy[v];
seg[2*v]+=lzy[v];
lzy[2*v+1]+=lzy[v];
seg[2*v+1]+=lzy[v];
lzy[v]=0;
}
void ins(int v,int a,int b,int l,int r,int x)
{
if(a<=l&&b>=r)
{
seg[v]+=x;
lzy[v]+=x;
return ;
}
if(r<a||l>b) return ;
push(v);
ins(2*v,a,b,l,(l+r)/2,x);
ins(2*v+1,a,b,(l+r)/2+1,r,x);
seg[v]=max(seg[2*v],seg[2*v+1]);
}
vector<int>countScans(vector<int>a,vector<int>X,vector<int>V)
{
set<pair<int,int>>S;
int n=sz(a),q=sz(X);
for(int i=0;i<n;i++) S.insert({a[i],i});
for(int i=0;i<q;i++) S.insert({V[i],X[i]});
int it=0;
for(int i=1;i<=pot;i++) seg[i+pot-1]=-inf;
for(auto x:S)
{
id[x.nd][x.st]=++it;
seg[it+pot-1]+=x.nd;
}
for(int i=0;i<n;i++) seg[id[i][a[i]]+pot-1]+=inf;
for(int i=pot-1;i>0;i--) seg[i]=max(seg[2*i],seg[2*i+1]);
for(int i=0;i<n;i++) ins(1,id[i][a[i]]+1,pot,1,pot,-1);
vector<int>ans(q);
for(int i=0;i<q;i++)
{
ins(1,id[X[i]][a[X[i]]]+1,pot,1,pot,1);
ins(1,id[X[i]][a[X[i]]],id[X[i]][a[X[i]]],1,pot,-inf);
a[X[i]]=V[i];
ins(1,id[X[i]][a[X[i]]],id[X[i]][a[X[i]]],1,pot,inf);
ins(1,id[X[i]][a[X[i]]]+1,pot,1,pot,-1);
ans[i]=seg[1];
}
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
vector<int>X=countScans({1,2, 3, 4},{0, 2},{3, 1});
for(auto x:X) cout<<x<<" ";
return 0;
}*/
