#include "bubblesort2.h"
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
using vi = vector<int>;
#define sz(x) int(x.size())
struct sdata
{
set<int> inds;
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 = -3'000'000;
s[i].count = 0;
}
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])
{
s[i].inds.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])
{
s[i].inds.erase(id);
s[i].count--;
s[i].currans = (s[i].inds.empty() ? -3'000'000 : *s[i].inds.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]);
}
}
};
vi countScans(vi A_, vi X, vi V)
{
A = A_;
N = sz(A);
Q = sz(X);
map<int, int> vals;
for(int i = 0; i < N; i++)
vals[A[i]] = 0;
for(int j = 0; j < Q; j++)
vals[V[j]] = 0;
int ct = -1;
for(auto& z : vals)
{
z.second = ++ct;
}
// cerr << "values # = " << sz(vals) << '\n';
vi answer(Q);
segtree S(N+Q);
for(int i = 0; i < N; i++)
{
// cerr << "insert " << i << " at " << vals[A[i]] << '\n';
S.insert(1, vals[A[i]], i);
}
for(int j = 0; j < Q; j++)
{
S.erase(1, vals[A[X[j]]], X[j]);
A[X[j]] = V[j];
S.insert(1, vals[A[X[j]]], X[j]);
answer[j] = S.s[1].currans;
}
return answer;
}
