#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 15e5 + 5;
int SZ;
int s[4 * N], lz[4 * N], cnt[4 * N];
void app(int id, int x) {
s[id] -= x;
lz[id] += x;
}
void psh(int id) {
if (lz[id]) {
app(id * 2, lz[id]);
app(id * 2 + 1, lz[id]);
lz[id] = 0;
}
}
void upd(int i, int x, int id = 1, int l = 1, int r = SZ, int rank = 0) {
if (l == r) {
if (x == -1) {
s[id] = 0;
cnt[id] = 0;
} else {
s[id] = x - rank;
cnt[id] = 1;
}
return;
}
psh(id);
int md = (l + r) / 2;
if (i <= md) {
app(id * 2 + 1, x == -1 ? -1 : 1);
upd(i, x, id * 2, l, md, rank);
} else {
upd(i, x, id * 2 + 1, md + 1, r, rank + cnt[id * 2]);
}
cnt[id] = cnt[id * 2] + cnt[id * 2 + 1];
s[id] = max(s[id * 2], s[id * 2 + 1]);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
int N = A.size(), Q = X.size();
vector<array<int, 2>> comp;
for (int i = 0; i < N; ++i) {
comp.push_back({A[i], i});
}
for (int i = 0; i < Q; ++i) {
comp.push_back({V[i], X[i]});
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
SZ = comp.size();
auto get = [&](int x, int i) {
return lower_bound(comp.begin(), comp.end(), array<int, 2>{x, i}) - comp.begin() + 1;
};
for (int i = 0; i < N; ++i) {
A[i] = get(A[i], i);
upd(A[i], i);
}
auto chg = [&](int u, int x) {
upd(A[u], -1);
A[u] = get(x, u);
upd(A[u], u);
};
vector<int> res(Q);
for (int i = 0; i < Q; ++i) {
chg(X[i], V[i]);
res[i] = s[1];
}
return res;
}
