#include "bubblesort2.h"
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) int(x.size())
set<int> inds[1'000'000];
struct sdata
{
int currans;
int count;
};
sdata combine(sdata X, sdata Y)
{
sdata res;
res.count = X.count + Y.count;
res.currans = max(X.currans, Y.currans - X.count);
return res;
}
int N, Q;
vi A;
struct segtree
{
int Z;
vi l, r;
vector<sdata> s;
void build(int i, int L, int R)
{
l[i] = L;
r[i] = R;
if(L == R)
{
s[i].currans = (inds[l[i]].empty() ? -3'000'000 : *inds[l[i]].rbegin());
s[i].count = sz(inds[l[i]]);
}
else
{
int m = (L+R)/2;
build(2*i, L, m);
build(2*i+1, m+1, R);
s[i] = combine(s[2*i], s[2*i+1]);
}
// cerr << L << ' ' << R << " : " << s[i].currans << ' ' << s[i].count << '\n';
}
segtree(int K)
{
Z = 4*K;
l = r = vi(1+Z);
s = vector<sdata>(1+Z);
build(1, 0, K-1);
}
void insert(int i, int p, int id)
{
if(l[i] == r[i])
{
inds[l[i]].insert(id);
s[i].currans = max(s[i].currans, id);
s[i].count++;
}
else
{
if(p <= (l[i]+r[i])/2)
insert(2*i, p, id);
else
insert(2*i+1, p, id);
s[i] = combine(s[2*i], s[2*i+1]);
}
// cerr << l[i] << ' ' << r[i] << " : " << s[i].currans << ' ' << s[i].count << '\n';
}
void erase(int i, int p, int id)
{
if(l[i] == r[i])
{
inds[l[i]].erase(id);
s[i].count--;
s[i].currans = (inds[l[i]].empty() ? -3'000'000 : *inds[l[i]].rbegin());
}
else
{
if(p <= (l[i]+r[i])/2)
erase(2*i, p, id);
else
erase(2*i+1, p, id);
s[i] = combine(s[2*i], s[2*i+1]);
}
// cerr << l[i] << ' ' << r[i] << " : " << s[i].currans << ' ' << s[i].count << '\n';
}
};
vi countScans(vi A_, vi X, vi V)
{
A = A_;
N = sz(A);
Q = sz(X);
map<pii, int> vals;
for(int i = 0; i < N; i++)
vals[{A[i], i}] = 0;
for(int j = 0; j < Q; j++)
vals[{V[j], X[j]}] = 0;
int ct = -1;
for(auto& z : vals)
{
z.second = ++ct;
// cerr << z.first.first << " - " << z.second << '\n';
}
// cerr << "values # = " << sz(vals) << '\n';
vi answer(Q);
for(int i = 0; i < N; i++)
inds[vals[{A[i], i}]].insert(i);
segtree S(N+Q);
// for(int i = 0; i < N; i++)
// {
// S.insert(1, vals[{A[i], i}], i);
// }
for(int j = 0; j < Q; j++)
{
S.erase(1, vals[{A[X[j]], X[j]}], X[j]);
A[X[j]] = V[j];
S.insert(1, vals[{A[X[j]], X[j]}], X[j]);
answer[j] = S.s[1].currans;
}
return answer;
}
