#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e6+5;
set<int> pos[nx];
int nod[nx<<2], la[nx<<2], pre[nx];
void build(int id, int l, int r)
{
la[id]=0;
if(l==r) return void(nod[id]=*pos[l].rbegin()-pre[l]);
int mid=(l+r)>>1;
build(id<<1, l, mid);
build(id<<1|1, mid+1, r);
nod[id]=max(nod[id<<1], nod[id<<1|1]);
}
void down(int id)
{
if(!la[id]) return;
for(int j = id*2; j <= id*2+1; j++)
la[j]+=la[id], nod[j]+=la[id];
la[id]=0;
}
void update(int id, int l, int r, int u, int v, int val)
{
if(l>v || r<u) return;
if(l>=u && r<=v)
{
nod[id]+=val;
la[id]+=val;
return;
}
int mid=(l+r)>>1;
down(id);
update(id<<1, l, mid, u, v, val);
update(id<<1|1, mid+1, r, u, v, val);
nod[id]=max(nod[id<<1], nod[id<<1|1]);
}
int get(int id, int l, int r, int u, int v)
{
if(l>v || r<u) return -inf;
if(l>=u && r<=v) return nod[id];
int mid=(l+r)>>1;
down(id);
return max(get(id<<1, l, mid, u, v), get(id<<1|1, mid+1, r, u, v));
}
vector<int> countScans(vector<int> a, vector<int> X, vector<int> V)
{
vector<int> rar;
rar.clear();
int n=a.size();
for(int i = 0; i < n; i++)
rar.emplace_back(a[i]);
int q=X.size();
for(int i = 0; i < q; i++)
rar.emplace_back(V[i]);
sort(rar.begin(), rar.end());
rar.erase(unique(rar.begin(), rar.end()), rar.end());
int m=rar.size();
pre[0]=0;
for(int i = 1; i <= m; i++)
pos[i].emplace(-inf), pre[i]=0;
for(int i = 0; i < n; i++)
{
a[i]=upper_bound(rar.begin(), rar.end(), a[i])-rar.begin();
pos[a[i]].emplace(i);
pre[a[i]]++;
}
for(int i = 1; i <= m; i++)
pre[i]+=pre[i-1];
build(1, 1, m);
vector<int> res;
res.clear();
// for(int j = 1; j <= m; j++)
// cout<<get(1, 1, m, j, j)<<' ';
// cout<<'\n';
for(int i = 0; i < q; i++)
{
int old=*pos[a[X[i]]].rbegin();
pos[a[X[i]]].erase(pos[a[X[i]]].find(X[i]));
int nw=*pos[a[X[i]]].rbegin();
update(1, 1, m, a[X[i]], a[X[i]], nw-old);
update(1, 1, m, a[X[i]], m, 1);
int val=upper_bound(rar.begin(), rar.end(), V[i])-rar.begin();
old=*pos[val].rbegin();
pos[val].emplace(X[i]);
nw=*pos[val].rbegin();
update(1, 1, m, val, val, nw-old);
update(1, 1, m, val, m, -1);
a[X[i]]=val;
res.emplace_back(nod[1]+1);
// for(int j = 1; j <= m; j++)
// cout<<get(1, 1, m, j, j)<<' ';
// cout<<'\n';
}
return res;
}
// signed main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("inputf.in", "r", stdin);
// freopen("outputf.out", "w", stdout);
// int n, q;
// cin>>n>>q;
// vector<int> a, x, v;
// a.clear(), x.clear(), v.clear();
// for(int i = 0; i < n; i++)
// {
// int p;
// cin>>p;
// a.emplace_back(p);
// }
// for(int i = 0; i < q; i++)
// {
// int l, r;
// cin>>l>>r;
// x.emplace_back(l);
// v.emplace_back(r);
// }
// vector<int> res=countScans(a, x, v);
// for(int x:res) cout<<x<<'\n';
// }
