#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
const int INF = 0x3f3f3f;
struct SegmentTree {
int Tmax[N << 3];
int Tcnt[N << 3];
int lazy[N << 3];
SegmentTree() {
memset(Tmax, -INF, sizeof Tmax);
}
void push(int i, int l, int r) {
Tmax[i] += lazy[i];
if (l != r) {
lazy[i << 1] += lazy[i], lazy[i << 1 | 1] += lazy[i];
}
lazy[i] = 0;
}
#define mid ((l + r) >> 1)
void updRange(int i, int l, int r, int L, int R, int x) {
push(i, l, r);
if (l > R || L > r) return;
if (L <= l && r <= R) {
lazy[i] = x, push(i, l, r); return;
}
updRange(i << 1, l, mid, L, R, x);
updRange(i << 1 | 1, mid + 1, r, L, R, x);
Tmax[i] = max(Tmax[i << 1], Tmax[i << 1 | 1]);
}
void updPos(int i, int l, int r, int p, int x, int y) {
push(i, l, r);
if (p > r || l > p) return;
if (l == r) { Tmax[i] = x, Tcnt[i] = y; return; }
updPos(i << 1, l, mid, p, x, y);
updPos(i << 1 | 1, mid + 1, r, p, x, y);
Tcnt[i] = Tcnt[i << 1] + Tcnt[i << 1 | 1];
Tmax[i] = max(Tmax[i << 1], Tmax[i << 1 | 1]);
}
int get(int i, int l, int r, int L, int R) {
if (l > R || L > r) return 0;
if (L <= l && r <= R) return Tcnt[i];
return get(i << 1, l, mid, L, R) + get(i << 1 | 1, mid + 1, r, L, R);
}
#undef mid
} IT;
struct Data {
int v, p, id;
bool operator < (const Data& rhs) const {
return v == rhs.v ? p < rhs.p : v < rhs.v;
}
};
int prv[N], pos[N];
vector<Data> vec;
vector<int> countScans(vector<int> a, vector<int> x, vector<int> y) {
int n = a.size(), m = x.size();
for (int i = 0; i < n; ++i) vec.push_back({a[i], i, i});
for (int i = 0; i < m; ++i) vec.push_back({y[i], x[i], i + n});
sort(vec.begin(), vec.end());
int sz = n + m;
for (int i = 0; i < sz; ++i) {
if (vec[i].id >= n) {
pos[vec[i].id - n] = i; continue;
}
int F = vec[i].p - IT.get(1, 0, sz - 1, 0, i);
IT.updPos(1, 0, sz - 1, i, F, 1), prv[vec[i].p] = i;
}
vector<int> res;
for (int i = 0; i < m; ++i) {
int &tmp = prv[x[i]];
IT.updRange(1, 0, sz - 1, tmp, sz - 1, 1);
IT.updPos(1, 0, sz - 1, tmp, -INF, 0);
tmp = pos[i];
int F = x[i] - IT.get(1, 0, sz - 1, 0, tmp);
IT.updRange(1, 0, sz - 1, tmp, sz - 1, -1);
IT.updPos(1, 0, sz - 1, tmp, F, 1);
res.push_back(IT.Tmax[1]);
}
return res;
}
