#include "bubblesort2.h"
#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int N = 1'000'010;
namespace seg {
int a[N];
void add(int l, int r, int x) {
Loop (i,l,r)
a[i] += x;
}
int get() {
int ans = 0;
Loop (i,0,N)
ans = max(ans, a[i]);
return ans;
}
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
int n = A.size();
int q = X.size();
vector<pii> cmp;
Loop (i,0,n)
cmp.push_back({A[i], i});
Loop (i,0,q)
cmp.push_back({V[i], X[i]});
sort(cmp.begin(), cmp.end());
cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
Loop (i,0,n)
A[i] = lower_bound(cmp.begin(), cmp.end(), pii{A[i], i}) - cmp.begin();
Loop (i,0,q)
V[i] = lower_bound(cmp.begin(), cmp.end(), pii{V[i], X[i]}) - cmp.begin();
Loop (i,0,n) {
seg::add(A[i], A[i]+1, i);
seg::add(A[i]+1, cmp.size(), -1);
}
vector<int> ans;
Loop (j,0,q) {
int i = X[j];
seg::add(A[i], A[i]+1, -i);
seg::add(A[i]+1, cmp.size(), 1);
A[i] = V[j];
seg::add(A[i], A[i]+1, i);
seg::add(A[i]+1, cmp.size(), -1);
ans.push_back(seg::get());
}
return ans;
}
