#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(), v.end()
const int BIG = 1e9 + 10;
struct segTree
{
vector<pii> tree;
int sz = 0;
void init(int n)
{
sz = 1;
while (sz < n)
sz *= 2;
tree.resize(2 * sz, {-BIG, 0});
}
void upd(int v, int val)
{
if (tree[v].f != -BIG)
{
tree[v].f += val;
tree[v].s += val;
}
}
void push(int v, int lv, int rv)
{
if (rv - lv == 1 or tree[v].s == 0)
return;
upd(v * 2 + 1, tree[v].s);
upd(v * 2 + 2, tree[v].s);
tree[v].s = 0;
}
void set(int pos, int val, int v, int lv, int rv)
{
push(v, lv, rv);
if (rv - lv == 1)
{
tree[v].f = val;
return;
}
int m = (lv + rv) >> 1;
if (pos < m)
set(pos, val, v * 2 + 1, lv, m);
else
set(pos, val, v * 2 + 2, m, rv);
tree[v].f = max(tree[v * 2 + 1].f, tree[v * 2 + 2].f);
}
void set(int pos, int val)
{
set(pos, val, 0, 0, sz);
}
void add(int l, int r, int x, int v, int lv, int rv)
{
push(v, lv, rv);
if (l <= lv and rv <= r)
{
upd(v, x);
return;
}
if (rv <= l or r <= lv)
return;
int m = (lv + rv) >> 1;
add(l, r, x, v * 2 + 1, lv, m);
add(l, r, x, v * 2 + 2, m, rv);
tree[v].f = max(tree[v * 2 + 1].f, tree[v * 2 + 2].f);
}
void add(int l, int r, int x)
{
add(l, r, x, 0, 0, sz);
}
};
struct segTreeSum
{
vector<ll> tree;
int sz;
void init(int n)
{
sz = n;
tree.resize(2 * sz);
}
void build(vector<int> &a)
{
init(a.size());
for (int i = 0; i < a.size(); ++i)
tree[i + sz] = a[sz];
for (int i = sz - 1; i > 0; --i)
tree[i] = tree[i << 1] + tree[(i << 1) + 1];
}
int get(int l, int r) // [l, r)
{
l += sz;
r += sz;
int res = 0;
while (l < r)
{
if (l & 1)
res += tree[l++];
if (r & 1)
res += tree[--r];
l >>= 1;
r >>= 1;
}
return res;
}
void add(int pos, int val)
{
pos += sz;
tree[pos] += val;
pos >>= 1;
while (pos)
{
tree[pos] = tree[pos << 1] + tree[(pos << 1) + 1];
pos >>= 1;
}
}
};
std::vector<int> countScans(std::vector<int> a, std::vector<int> x, std::vector<int> v)
{
int n = a.size();
int q = x.size();
std::vector<int> answer(q);
vector<int> VALS;
for (int i = 0; i < n; ++i)
VALS.pb(a[i]);
for (int i = 0; i < q; ++i)
VALS.pb(v[i]);
sort(all(VALS));
map<int, int> cnt;
for (int i = 0; i < n; ++i)
a[i] = lower_bound(all(VALS), a[i]) - VALS.begin() + (cnt[a[i]]++);
for (int i = 0; i < q; ++i)
v[i] = lower_bound(all(VALS), v[i]) - VALS.begin() + (cnt[v[i]]++);
vector<int> l(VALS.size());
vector<int> r(VALS.size());
for (int p = 0; p < VALS.size(); ++p)
{
int curL = p;
while (p + 1 < VALS.size() and VALS[p + 1] == VALS[p])
p++;
for (int j = curL; j <= p; ++j)
l[j] = curL, r[j] = p;
}
segTree tree;
segTreeSum cntEls;
tree.init(VALS.size());
cntEls.init(VALS.size());
for (int i = 0; i < n; ++i)
{
// cerr << a[i] << " : " << i + 1 << "\n";
tree.set(a[i], i + 1);
cntEls.add(a[i], 1);
}
for (int i = 0; i < n; ++i)
{
// cerr << l[a[i]] << " " << VALS.size() << " : " << -1 << "\n";
tree.add(l[a[i]], VALS.size(), -1);
}
for (int j = 0; j < q; j++)
{
int i = x[j];
tree.set(a[i], -BIG);
cntEls.add(a[i], -1);
tree.add(l[a[i]], VALS.size(), 1);
a[i] = v[j];
tree.add(l[a[i]], VALS.size(), -1);
cntEls.add(a[i], 1);
tree.set(a[i], i + 1 - cntEls.get(0, r[a[i]] + 1));
// tree.add(0, lower_bound(all(VALS), a[i]) - VALS.begin(), -1);
answer[j] = tree.tree[0].f;
}
return answer;
}
