#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
// void setup()
// {
// #ifndef ONLINE_JUDGE
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// #endif
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// }
int n, tree[4000000], rem[4000000];
pair<int, int> p[1000000];
inline void Update(int ind, int l, int r, int x, int y, int v)
{
if (y < x || r < x || y < l)
{
return;
}
if (x <= l && r <= y)
{
rem[ind] += v;
tree[ind] += v;
return;
}
int m = (l + r) >> 1;
Update(ind << 1, l, m, x, y, v);
Update(ind << 1 | 1, m + 1, r, x, y, v);
tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]) + rem[ind];
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
vector<int> res;
for (int i = 0; i < A.size(); ++i)
{
p[n++] = {A[i], i};
}
for (int i = 0; i < V.size(); ++i)
{
p[n++] = {V[i], X[i]};
}
sort(p, p + n);
n = unique(p, p + n) - p;
for (int i = 0; i < A.size(); ++i)
{
A[i] = lower_bound(p, p + n, make_pair(A[i], i)) - p + 1;
Update(1, 1, n, A[i], A[i], i);
Update(1, 1, n, A[i] + 1, n, -1);
}
for (int i = 0; i < V.size(); ++i)
{
V[i] = lower_bound(p, p + n, make_pair(V[i], X[i])) - p + 1;
Update(1, 1, n, A[X[i]], A[X[i]], -X[i]);
Update(1, 1, n, A[X[i]] + 1, n, 1);
Update(1, 1, n, V[i], V[i], X[i]);
Update(1, 1, n, V[i] + 1, n, -1);
A[X[i]] = V[i];
res.push_back(tree[1]);
}
return res;
}
// int main()
// {
// setup();
// return 0;
// }
