#include "bubblesort2.h"
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int n, q, k;
pii comp[1000000];
const int inf = 1e8;
int seg[1 << 21];
int lay[1 << 21];
int fen[1000001];
void updatePoint(int i, int s, int e, int x, int v) {
if (s == e) {
seg[i] = v;
lay[i] = 0;
return;
}
seg[i << 1] += lay[i];
seg[i << 1 | 1] += lay[i];
lay[i << 1] += lay[i];
lay[i << 1 | 1] += lay[i];
lay[i] = 0;
int m = (s + e) / 2;
if (x <= m) updatePoint(i << 1, s, m, x, v);
else updatePoint(i << 1 | 1, m + 1, e, x, v);
seg[i] = max(seg[i << 1], seg[i << 1 | 1]) + lay[i];
}
void updateRange(int i, int s, int e, int x, int y, int v) {
if (e < x || y < s) return;
if (x <= s && e <= y) {
seg[i] += v;
lay[i] += v;
return;
}
int m = (s + e) / 2;
updateRange(i << 1, s, m, x, y, v);
updateRange(i << 1 | 1, m + 1, e, x, y, v);
seg[i] = max(seg[i << 1], seg[i << 1 | 1]) + lay[i];
}
void update(int i, int x) {
while (i <= k) {
fen[i] += x;
i += i & -i;
}
}
int query(int i) {
int ret = 0;
while (i) {
ret += fen[i];
i -= i & -i;
}
return ret;
}
int find(int i, int x) {
return lower_bound(comp, comp + k, pii(x, i)) - comp + 1;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
for (int i = 0; i < (1 << 21); ++i) seg[i] = lay[i] = -inf;
n = A.size();
q = X.size();
for (int i = 0; i < n; ++i) comp[k++] = pii(A[i], i);
for (int i = 0; i < q; ++i) comp[k++] = pii(V[i], X[i]);
sort(comp, comp + k);
k = unique(comp, comp + k) - comp;
for (int i = 0; i < n; ++i) {
A[i] = find(i, A[i]);
update(A[i], 1);
}
for (int i = 0; i < q; ++i) {
V[i] = find(X[i], V[i]);
}
for (int i = 0; i < n; ++i) {
updatePoint(1, 1, k, A[i], i - query(A[i] - 1));
}
vector<int> ret(q);
for (int it = 0; it < q; ++it) {
int i = X[it];
int x = V[it];
update(A[i], -1);
updateRange(1, 1, k, A[i], k, 1);
updatePoint(1, 1, k, A[i], -inf);
A[i] = x;
update(A[i], 1);
updateRange(1, 1, k, A[i], k, -1);
updatePoint(1, 1, k, A[i], i - query(A[i] - 1));
ret[it] = seg[1];
}
return ret;
}
