#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif
const int INF = int(1e8), N = int(1e6) + 5;
int n, m, q;
int s[4 * N], lz[4 * N];
void app(int id, int x) {
s[id] += x;
lz[id] += x;
}
void psh(int id) {
app(id * 2, lz[id]);
app(id * 2 + 1, lz[id]);
lz[id] = 0;
}
void change(int i, int v, int x) {
int id = 1, l = 1, r = m;
while (l ^ r) {
int md = (l + r) / 2;
if (lz[id]) {
psh(id);
}
id *= 2;
if (i <= md) {
app(id + 1, x);
r = md;
} else {
l = md + 1;
id += 1;
}
}
s[id] += v;
while (id > 1) {
id /= 2;
s[id] = max(s[id * 2], s[id * 2 + 1]);
}
}
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
n = int(A.size());
q = int(X.size());
vector<int> res(q);
vector<pair<int, int>> values;
for (int i = 0; i < n; ++i) {
values.emplace_back(A[i], i);
}
for (int i = 0; i < q; ++i) {
values.emplace_back(V[i], X[i]);
}
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
auto upd = [&](int pos, int i, int x) {
int v = pos;
pos = lower_bound(values.begin(), values.end(), make_pair(pos, i)) - values.begin() + 1;
change(pos, x * (i + INF), -x);
};
m = int(values.size());
for (int i = 1; i < 4 * m; ++i) {
s[i] = -INF;
}
for (int i = 0; i < n; ++i) {
upd(A[i], i, 1);
}
for (int i = 0; i < q; ++i) {
upd(A[X[i]], X[i], -1);
upd(V[i], X[i], 1);
res[i] = s[1];
A[X[i]] = V[i];
}
return res;
}
