#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ost = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using tupl = tuple<int, int, int, int>;
using pii = pair<int, int>;
const int inf = INT32_MIN / 2;
struct state {
int max, lazyAdd;
void merge(state &l, state &r) {
max = std::max(l.max, r.max);
}
void push(state &l, state &r) {
l.apply(lazyAdd);
r.apply(lazyAdd);
lazyAdd = 0;
}
void apply(int x) {
max += x;
lazyAdd += x;
}
};
struct segtree {
public:
int n, lim;
vector<state> a;
vector<int> mapping;
segtree(int n, int lim, vector<tupl> &x) : n(n), lim(lim), a(4 * n), mapping(n) {
build(0, n - 1, 1, x);
}
void build(int l, int r, int v, vector<tupl> &x) {
if (l == r) {
if (get<2>(x[l]) < lim) {
a[v].apply(get<1>(x[l]) - get<3>(x[l]));
} else {
a[v].apply(inf);
}
mapping[l] = v;
} else {
int m = (l + r) / 2;
build(l, m, 2 * v, x);
build(m + 1, r, 2 * v + 1, x);
a[v].merge(a[2 * v], a[2 * v + 1]);
}
}
void upd(int ql, int qr, int l, int r, int v, int x) {
if (qr < l || r < ql) return;
else if (ql <= l && r <= qr) a[v].apply(x);
else {
int m = (l + r) / 2;
upd(ql, qr, l, m, 2 * v, x);
upd(ql, qr, m + 1, r, 2 * v + 1, x);
a[v].merge(a[2 * v], a[2 * v + 1]);
}
}
void upd(int ql, int qr, int x) {
assert(0 <= ql && ql <= qr && qr < n);
return upd(ql, qr, 0, n - 1, 1, x);
}
void set(int i, int x) {
i = mapping[i];
a[i].lazyAdd = x;
a[i].max = x;
for(; i > 1; i /= 2) a[i / 2].merge(a[i], a[i ^ 1]);
}
state& at(int i) {
return a[mapping[i]];
}
void print() {
for (int i = 0; i < n; i++) {
cout << a[mapping[i]].lazyAdd << " ";
}
cout << endl;
}
};
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
int q = x.size(), n = a.size();
vector<tupl> entries;
entries.reserve(n + q);
ost<pii> oset;
for (int i = 0; i < n; i++) oset.insert({a[i], i});
for (int i = 0; i < n; i++) entries.push_back({a[i], i, i, oset.order_of_key({a[i], i})});
for (int i = 0; i < q; i++) {
bool removed = oset.erase({a[x[i]], x[i]});
assert(removed);
oset.insert({v[i], x[i]});
entries.push_back({v[i], x[i], i + n, oset.order_of_key({v[i], x[i]})});
a[x[i]] = v[i];
}
sort(entries.begin(), entries.end());
vector<int> where(n + q);
for (int i = 0; i < n + q; i++) where[get<2>(entries[i])] = i;
vector<int> cur(n);
copy(where.begin(), where.begin() + n, cur.begin());
segtree tree(n + q, n, entries);
vector<int> answer(q);
for (int i = 0; i < q; i++) {
int prev = cur[x[i]];
int now = where[i + n];
tupl& ptr = entries[now];
tree.set(prev, inf);
tree.set(now, get<1>(ptr) - get<3>(ptr));
if (prev < now - 1) {
tree.upd(prev + 1, now - 1, 1);
} else if (prev > now +1) {
tree.upd(now + 1, prev - 1, -1);
}
// tree.print();
// for (tupl& i : entries) cout << "{" << get<0>(i) << ", " << get<1>(i) << ", " << get<3>(i) << "} ";
// cout << endl;
cur[x[i]] = now;
answer[i] = tree.a[1].max;
}
return answer;
}
