#include "bubblesort2.h"
using namespace std;
typedef vector<int> vi;
const int N = 500000, Q = 500000, N_ = N + Q + 1;
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int aa[N];
int zz[N_ + 1], ll[N_ + 1], rr[N_ + 1], ii[N_ + 1], sz[N_ + 1], xx[N_ + 1], _, u_, l_, r_;
int node(int i) {
static int _ = 1;
zz[_] = rand_();
ii[_] = i;
sz[_] = 1;
xx[_] = i + 1;
return _++;
}
void pul(int u) {
int l = ll[u], r = rr[u];
sz[u] = sz[l] + 1 + sz[r];
xx[u] = max(max(xx[l], ii[u]) + 1 + sz[r], xx[r]);
}
void split(int u, int i) {
int c;
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
c = aa[ii[u]] != aa[i] ? aa[ii[u]] - aa[i] : ii[u] - i;
if (c < 0) {
split(rr[u], i);
rr[u] = l_, l_ = u;
} else if (c > 0) {
split(ll[u], i);
ll[u] = r_, r_ = u;
} else {
u_ = u, l_ = ll[u], r_ = rr[u];
ll[u] = rr[u] = 0;
}
pul(u);
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v), pul(u);
return u;
} else {
ll[v] = merge(u, ll[v]), pul(v);
return v;
}
}
void tr_add(int i) {
split(u_, i);
u_ = merge(merge(l_, node(i)), r_);
}
void tr_remove(int i) {
split(u_, i);
u_ = merge(l_, r_);
}
vi countScans(vi aa_, vi ii, vi bb) {
int n = aa_.size();
for (int i = 0; i < n; i++)
aa[i] = aa_[i];
for (int i = 0; i < n; i++)
tr_add(i);
int q = ii.size();
vi ans(q);
for (int h = 0; h < q; h++) {
int i = ii[h], b = bb[h];
tr_remove(i);
aa[i] = b;
tr_add(i);
ans[h] = xx[u_] - n;
}
return ans;
}
