#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 t[4*N];
int mx[4*N];
void add(int l, int r, int x, int i, int b, int e) {
if (l <= b && e <= r) {
t[i] += x;
mx[i] += x;
return;
}
if (r <= b || e <= l)
return;
add(l, r, x, 2*i+1, b, (b+e)/2);
add(l, r, x, 2*i+2, (b+e)/2, e);
mx[i] = t[i] + max(mx[2*i+1], mx[2*i+2]);
}
void add(int l, int r, int x) { add(l, r, x, 0, 0, N); }
int get() { return mx[0]; }
}
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;
}
