#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 5e5 + 7;
int tree[mxN * 8], lazy[mxN * 8];
vector<ii> val;
void Down(int j)
{
tree[j * 2] += lazy[j];
lazy[j * 2] += lazy[j];
tree[j * 2 + 1] += lazy[j];
lazy[j * 2 + 1] += lazy[j];
lazy[j] = 0;
}
void Upd(int u, int v, int inc, int j = 1, int l = 0, int r = val.size() - 1)
{
if (u > r || l > v)
return;
if (u <= l && r <= v)
{
tree[j] += inc;
lazy[j] += inc;
return;
}
Down(j);
int mid = (l + r) / 2;
Upd(u, v, inc, j * 2, l, mid);
Upd(u, v, inc, j * 2 + 1, mid + 1, r);
tree[j] = max(tree[j * 2], tree[j * 2 + 1]);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
for (int i = 0; i < A.size(); i++)
val.push_back({A[i], i});
for (int i = 0; i < X.size(); i++)
val.push_back({V[i], X[i]});
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
for (int i = 0; i < A.size(); i++)
{
int j = lower_bound(val.begin(), val.end(), ii(A[i], i)) - val.begin();
Upd(j, j, i);
Upd(j + 1, val.size(), -1);
}
vector<int> answer(X.size());
for (int i = 0; i < X.size(); i++)
{
int j = lower_bound(val.begin(), val.end(), ii(A[X[i]], X[i])) - val.begin();
Upd(j, j, -X[i]);
Upd(j + 1, val.size(), 1);
A[X[i]] = V[i];
j = lower_bound(val.begin(), val.end(), ii(A[X[i]], X[i])) - val.begin();
Upd(j, j, X[i]);
Upd(j + 1, val.size(), -1);
answer[i] = tree[1];
}
return answer;
}
