#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Nmax = 1e6 + 5;
const ll inf = 1e9;
struct node
{
int cnt;
ll maxval;
};
node unite(node st, node dr)
{
node ans;
ans.cnt = st.cnt + dr.cnt;
ans.maxval = max(st.maxval + dr.cnt, dr.maxval);
return ans;
}
int repr[Nmax];
node aint[4 * Nmax];
set < int > poz[Nmax];
void build(int nod, int l, int r)
{
if (l == r)
{
if (repr[l] == 0)
{
aint[nod].cnt = poz[l].size();
aint[nod].maxval = -inf;
}
else
{
aint[nod].cnt = poz[l].size();
aint[nod].maxval = repr[l];
}
return;
}
int mid = (l + r) / 2;
build(2 * nod, l, mid);
build(2 * nod + 1, mid + 1, r);
aint[nod] = unite(aint[2 * nod], aint[2 * nod + 1]);
return;
}
void update(int nod, int l, int r, int x, int val)
{
if (l == r)
{
if (val == 0)
{
aint[nod].cnt = poz[l].size();
aint[nod].maxval = -inf;
}
else
{
aint[nod].cnt = poz[l].size();
aint[nod].maxval = val;
}
return;
}
int mid = (l + r) / 2;
if (x <= mid) update(2 * nod, l, mid, x, val);
else update(2 * nod + 1, mid + 1, r, x, val);
aint[nod] = unite(aint[2 * nod], aint[2 * nod + 1]);
return;
}
vector < int > countScans(vector < int > a, vector < int > x, vector < int > v)
{
int n = a.size(), q = x.size();
map < int, vector < pair < int, int >>> nrm;
for (int i = 0; i < n; i++) nrm[a[i]].push_back({
i,
0
});
for (int i = 0; i < q; i++) nrm[v[i]].push_back({
i,
1
});
int nrc = 0;
for (auto[val, V]: nrm)
{
nrc++;
for (auto[id, tip]: V)
{
if (tip == 0) a[id] = nrc;
else v[id] = nrc;
}
}
for (int i = 0; i < n; i++) poz[a[i]].insert(i + 1);
for (int i = 1; i <= nrc; i++)
{
if (!poz[i].empty()) repr[i] = ( * poz[i].rbegin());
}
build(1, 1, nrc);
vector < int > ans(q, 0);
for (int i = 0; i < q; i++)
{
int cur = a[x[i]];
a[x[i]]=v[i];
poz[cur].erase(poz[cur].find(x[i] + 1));
int nw;
if (poz[cur].empty()) nw = 0;
else nw = ( * poz[cur].rbegin());
assert(0<cur && 0<v[i] && cur <= nrc && v[i] <= nrc);
update(1, 1, nrc, cur, nw);
repr[cur] = nw;
poz[v[i]].insert(x[i] + 1);
nw = ( * poz[v[i]].rbegin());
update(1, 1, nrc, v[i], nw);
repr[v[i]] = nw;
ans[i] = aint[1].maxval - n;
}
return ans;
}/*
int main()
{
int n, q;
cin >> n >> q;
vector < int > a(n), x(q), v(q);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < q; i++) cin >> x[i] >> v[i];
vector < int > ans = countScans(a, x, v);
for (int x: ans) cout << x << '\n';
return 0;
}*/
