#include <bits/stdc++.h>
#include <bubblesort2.h>
#define pb push_back
using namespace std;
const int MAXN = 500000;
const int K = 10000000;
int n, q;
int a[MAXN*2+5];
int cpy[MAXN*2+5];
class Seg{
private:
int arr[MAXN*2*4+5];
int tag[MAXN*2*4+5];
void pull(int now) {
arr[now] = max(arr[now*2], arr[now*2+1]);
}
void push(int now, int len) {
if (!tag[now]) return;
arr[now] += tag[now];
if (len > 1) {
tag[now*2 ] += tag[now];
tag[now*2+1] += tag[now];
}
tag[now] = 0;
}
public:
void build(int now=1, int l=1, int r=MAXN*2) {
tag[now] = 0;
if (l == r) {
arr[now] = 0;
return;
}
int mid = (l + r) >> 1;
build(now*2 , l, mid);
build(now*2+1,mid+1,r);
pull(now);
return;
}
void mdy(int ml, int mr, int k, int now=1, int l=1, int r=MAXN*2) {
push(now, r-l+1);
if (l >= ml && r <= mr) {
tag[now] += k;
push(now, r-l+1);
return;
} else if (l > mr || r < ml) return;
int mid = (l + r) >> 1;
mdy(ml, mr, k, now*2 , l, mid);
mdy(ml, mr, k, now*2+1,mid+1,r);
pull(now);
}
int qry(int ql, int qr, int now=1, int l=1, int r=MAXN*2) {
push(now, r-l+1);
if (l >= ql && r <= qr) {
return arr[now];
} else if (l > qr || r < ql) return -MAXN*2;
int mid = (l + r) >> 1, tmp = -MAXN*2;
tmp = max(tmp, qry(ql, qr, now*2 , l, mid));
tmp = max(tmp, qry(ql, qr, now*2+1,mid+1,r));
pull(now);
return tmp;
}
} seg;
vector <signed> countScans(vector <signed> A, vector <signed> X, vector <signed> Y) {
int n = A.size(), q = Y.size();
for (int i = 0; i < n; i++)
cpy[i] = A[i] * K + i;
for (int i = 0; i < q; i++)
cpy[i+n] = Y[i] * K + X[i];
sort(cpy, cpy+n+q);
seg.build();
for (int i = 0; i < n; i++) {
A[i] = lower_bound(cpy, cpy+n+q, A[i] * K + i) - cpy + 1;
seg.mdy(A[i], A[i], i);
seg.mdy(A[i]+1, n+q, -1);
}
vector <signed> ans;
for (int i = 0; i < q; i++) {
Y[i] = lower_bound(cpy, cpy+n+q, Y[i] * K + X[i]) - cpy + 1;
seg.mdy(A[X[i]], A[X[i]], -X[i]);
seg.mdy(A[X[i]]+1, n+q, 1);
seg.mdy(Y[i], Y[i], X[i]);
seg.mdy(Y[i]+1, n+q, -1);
A[X[i]] = Y[i];
ans.pb(seg.qry(1, MAXN*2));
}
return ans;
}
