#include "bubblesort2.h"
#include <bits/stdc++.h>
#define pii pair <int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
using namespace std;
const int N = 1e6 + 5;
int sz;
struct lazy {
int seg[4 * N], lazy[4 * N];
void push(int l, int r, int i){
seg[i] += lazy[i];
if (l != r) lazy[2 * i] += lazy[i], lazy[2 * i + 1] += lazy[i];
lazy[i] = 0;
}
void update(int l, int r, int i, int ll, int rr, int val){
push(l, r, i);
if (l >= ll && r <= rr) return lazy[i] += val, push(l, r, i), void();
if (r < ll || l > rr) return;
int mid = (l + r) / 2;
update(l, mid, 2 * i, ll, rr, val), update(mid + 1, r, 2 * i + 1, ll, rr, val);
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
int query(int l, int r, int i, int ll, int rr){
push(l, r, i);
if (l >= ll && r <= rr) return seg[i];
if (r < ll || l > rr) return 0;
int mid = (l + r) / 2;
return max(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr));
}
} seg;
void printseg(){
for (int i = 1; i <= sz; i++) {
}
}
vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
int q=x.size(), n = a.size();
vector <int> ans(q);
vector <pii> comp;
for (int i = 0; i < n; i++) {
comp.emb(a[i], i);
}
for (int i = 0; i < q; i++) {
comp.emb(v[i], x[i]);
}
sort(all(comp));
sz = comp.size();
for (int i = 0; i < n; i++) {
int idx = lower_bound(all(comp), make_pair(a[i], i)) - comp.begin() + 1;
seg.update(1, sz, 1, idx, idx, i + 1);
seg.update(1, sz, 1, idx + 1, sz, -1);
}
// cout << "INIT: ";
for (int i = 0; i < q; i++) {
pii pre = {a[x[i]], x[i]};
int idx = lower_bound(all(comp), pre) - comp.begin() + 1;
seg.update(1, sz, 1, idx, idx, -x[i] - 1);
seg.update(1, sz, 1, idx + 1, sz, 1);
a[x[i]] = v[i];
idx = lower_bound(all(comp), make_pair(v[i], x[i])) - comp.begin() + 1;
seg.update(1, sz, 1, idx, idx, x[i] + 1);
seg.update(1, sz, 1, idx + 1, sz, -1);
ans[i] = (seg.query(1, sz, 1, 1, sz) - 1);
}
return ans;
}
/*
4 2
1 2 3 4
0 3
2 1
*/
