#include "bubblesort2.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
#define int long long
const int N = 1e6 + 5;
struct ST{
int tree[1 << 21], p[1 << 21];
void push(int x, int lx, int rx){
if(lx == rx || !p[x]) return;
tree[x<<1] += p[x], tree[x<<1|1] += p[x];
p[x<<1] += p[x], p[x<<1|1] += p[x];
p[x] = 0;
}
void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
tree[x] += v, p[x] += v;
return;
} push(x, lx, rx);
int m = (lx + rx) >> 1;
add(l, r, v, lx, m, x<<1), add(l, r, v, m+1, rx, x<<1|1);
tree[x] = max(tree[x<<1], tree[x<<1|1]);
}
}tree;
#define i32 int32_t
vector<i32> countScans(vector<i32> X, vector<i32> in, vector<i32> Y){
vector<int> a, val;
for(auto x : X) a.push_back(x);
for(auto x : Y) val.push_back(x);
int n = (int)a.size(), q = (int)in.size();
map<int, int> mm;
for(int i=0;i<n;i++) a[i] = a[i] * n + i, mm[a[i]];
for(int i=0;i<q;i++) val[i] = val[i] * n + in[i], mm[val[i]];
{
int in = 0;
for(auto& x : mm) x.second = in++;
for(int i=0;i<n;i++) a[i] = mm[a[i]];
for(int i=0;i<q;i++) val[i] = mm[val[i]];
}
for(int i=0;i<n;i++) tree.add(a[i], a[i], i), tree.add(a[i] + 1, N, -1);
vector<i32> res;
for(int j=0;j<q;j++){
int i = in[j], v = val[j];
tree.add(a[i] + 1, N, +1);
tree.add(a[i], a[i], -i);
a[i] = v;
tree.add(a[i], a[i], i);
tree.add(a[i] + 1, N, -1);
res.push_back(tree.tree[1]);
} return res;
}
/*
4 2
1 2 3 4
0 3
2 1
*/
