#include "bubblesort2.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 500055;
const int MAXQ = 500055;
const int MAXC = MAXN+MAXQ;
struct SEG {
SEG() { init(); }
int ds[MAXC*4], dmx[MAXC*4];
void init() {
fill(dmx, dmx+MAXC*4, -INF);
}
void prop(int i, int s, int e) {
if(!ds[i]) return;
if(s != e) {
ds[i<<1] += ds[i];
ds[i<<1|1] += ds[i];
}
dmx[i] += ds[i];
ds[i] = 0;
}
void cal(int i) {
dmx[i] = max(dmx[i<<1], dmx[i<<1|1]);
}
void upd(int i, int s, int e, int p, int q, int r) {
prop(i, s, e);
if(q < p || e < p || q < s) return;
if(p <= s && e <= q) {
ds[i] += r;
prop(i, s, e);
return;
}
int m = (s+e) >> 1;
upd(i<<1, s, m, p, q, r);
upd(i<<1|1, m+1, e, p, q, r);
cal(i);
}
int get() { return dmx[1]; }
} seg;
vector<pii> PV;
int A[MAXN], B[MAXQ], C[MAXQ];
int Ans[MAXQ];
int N, Q, L;
void solve() {
for(int i = 0; i < N; i++) PV.eb(A[i], i);
for(int i = 0; i < Q; i++) PV.eb(B[i], C[i]);
sorv(PV); univ(PV);
L = sz(PV);
for(int i = 0, j; i < N; i++) {
j = int(lower_bound(allv(PV), pii(A[i], i)) - PV.begin());
seg.upd(1, 0, L-1, j, j, INF+i);
seg.upd(1, 0, L-1, j+1, L-1, -1);
A[i] = j;
}
for(int i = 0, j, k; i < Q; i++) {
j = int(lower_bound(allv(PV), pii(B[i], C[i])) - PV.begin());
k = A[C[i]];
seg.upd(1, 0, L-1, k, k, -INF-C[i]);
seg.upd(1, 0, L-1, k+1, L-1, 1);
seg.upd(1, 0, L-1, j, j, INF+C[i]);
seg.upd(1, 0, L-1, j+1, L-1, -1);
A[C[i]] = j;
Ans[i] = seg.get();
}
}
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V) {
::N = sz(A); ::Q = sz(X);
for(int i = 0; i < N; i++) ::A[i] = A[i];
for(int i = 0; i < Q; i++) {
::C[i] = X[i];
::B[i] = V[i];
}
solve();
vector<int> ret(Q);
for(int i = 0; i < Q; i++) ret[i] = Ans[i];
return ret;
}
