#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
constexpr int maxn = 1<<20, B = 700, inf = 0x3f3f3f3f; // subtasks brutao, mudar
struct SegmentTree {
int tree[maxn], lazy[maxn], a[maxn];
void flush(int node, int i, int j) {
if(!lazy[node]) return;
if(i != j) {
lazy[node<<1] += lazy[node];
lazy[node<<1|1] += lazy[node];
}
tree[node] += lazy[node];
lazy[node] = 0;
}
void build(int node, int i, int j) {
lazy[node] = 0;
if(i == j) return (void)(tree[node] = a[i]);
int m = (i+j) >> 1;
build(node<<1, i, m);
build(node<<1|1, m+1, j);
tree[node] = max(tree[node<<1], tree[node<<1|1]);
}
void upd(int node, int i, int j, int l, int r, int v) {
flush(node, i, j);
if(i > r || j < l) return;
if(i >= l && j <= r) {
lazy[node] += v;
flush(node, i, j);
return;
}
int m = (i+j) >> 1;
upd(node<<1, i, m, l, r, v);
upd(node<<1|1, m+1, j, l, r, v);
tree[node] = max(tree[node<<1], tree[node<<1|1]);
}
int query() { return tree[1] + lazy[1]; } // quero o maximo geral mesmo
} seg;
void compress(vector<int>& A, vector<int>& V) {
map<int,int> mp;
for(int x : A)
mp[x] = 0;
for(int x : V)
mp[x] = 0;
int coord = 0;
for(auto& it : mp)
it.second = ++coord;
for(int& x : A)
x = mp[x];
for(int& x : V)
x = mp[x];
}
struct BIT {
int bit[maxn];
void upd(int x, int v) {
for(; x > 0; x -= x&-x)
bit[x] += v;
}
int query(int x) {
int ans = 0;
for(; x < maxn; x += x&-x)
ans += bit[x];
return ans;
}
void clear() { memset(bit, 0, sizeof bit); }
} bit;
vector<int> pareto;
int ans[maxn];
vector<pair<int,int>> qr[maxn];
void rebuild(const vector<int>& A) {
pareto.clear();
int N = (int)(A.size());
for(int i = 0; i < N; i++) {
if(A[i] == -1) continue;
while(pareto.size() && A[i] <= A[pareto.back()])
pareto.pop_back();
pareto.push_back(i);
}
/* puts("PARETO");
for(int x : pareto)
printf("%d ", x);
puts(""); */
bit.clear();
for(int i = 0; i < (int)A.size(); i++) {
while(qr[i].size()) {
auto [val, id] = qr[i].back();
qr[i].pop_back();
ans[id] = bit.query(val+1);
// printf("%d %d -> %d\n", i, val, ans[id]);
}
if(A[i] != -1) seg.a[i] = bit.query(A[i]+1), bit.upd(A[i], 1);
else seg.a[i] = -inf;
}
seg.build(1, 0, N-1);
}
int bs(int x, const vector<int>& A) {
int l = 0, r = (int)(pareto.size())-1, ans = -1;
while(l <= r) {
int m = (l+r) >> 1;
if(A[pareto[m]] < x)
ans = pareto[m], l = m+1;
else
r = m-1;
}
return ans;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int Q = (int)X.size(), N = (int)A.size();
compress(A, V);
std::vector<int> answer(Q);
for(int q = 0; q < Q; q++) {
A[X[q]] = -1;
qr[X[q]] = {{V[q], q}};
rebuild(A);
A[X[q]] = V[q];
int last = bs(V[q], A);
// printf("%d %d -> %d\n", X[q], V[q], last);
if(last > X[q])
seg.upd(1, 0, N-1, X[q], last, 1);
answer[q] = max(seg.query(), ans[q]);
}
return answer;
}
