#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int maxn[MAXN * 4 + 10], lazy[MAXN * 4 + 10];
void pushup(int rt) { maxn[rt] = max(maxn[rt << 1], maxn[rt << 1 | 1]); }
void pushdown(int rt)
{
if (lazy[rt])
{
maxn[rt << 1] += lazy[rt], maxn[rt << 1 | 1] += lazy[rt];
lazy[rt << 1] += lazy[rt], lazy[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
}
}
void update(int L, int R, int I, int l = 1, int r = MAXN, int rt = 1)
{
if (L <= l && r <= R)
{
maxn[rt] += I, lazy[rt] += I;
return;
}
int m = (l + r) / 2;
pushdown(rt);
if (L <= m)
update(L, R, I, l, m, rt << 1);
if (R > m)
update(L, R, I, m + 1, r, rt << 1 | 1);
pushup(rt);
}
int query(int L, int R, int l = 1, int r = MAXN, int rt = 1)
{
if (L <= l && r <= R)
return maxn[rt];
int m = (l + r) / 2, ans = -1e9, placed = 0;
pushdown(rt);
if (L <= m)
{
ans = query(L, R, l, m, rt << 1);
placed = 1;
}
if (R > m)
{
if (placed)
ans = max(ans, query(L, R, m + 1, r, rt << 1 | 1));
else
ans = query(L, R, m + 1, r, rt << 1 | 1);
}
return ans;
}
void p_update(int x, int I, int len = MAXN)
{
int v = query(x, x);
update(x, x, I - v);
}
typedef pair<int, int> pr;
#define mp make_pair
pr pool[MAXN];
int tot;
struct BIT
{
int t[MAXN + 20];
void update(int x, int I)
{
while (x <= MAXN)
t[x] += I, x += x & -x;
}
int query(int x)
{
int ans = 0;
while (x)
ans += t[x], x -= x & -x;
return ans;
}
} T;
void compress(int &x, int id)
{
x = lower_bound(pool + 1, pool + tot + 1, mp(x, id)) - pool;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
int Q = X.size(), N = A.size();
vector<int> answer(Q);
for (int i = 0; i < N; i++)
pool[++tot] = mp(A[i], i);
for (int i = 0; i < Q; i++)
pool[++tot] = mp(V[i], X[i]);
sort(pool + 1, pool + tot + 1);
tot = unique(pool + 1, pool + tot + 1) - pool - 1;
for (int i = 0; i < N; i++)
compress(A[i], i), T.update(A[i], 1);
for (int i = 0; i < Q; i++)
compress(V[i], X[i]);
for (int i = 0; i < 4 * MAXN + 10; i++)
maxn[i] = -1e7;
for (int i = 0; i < N; i++)
{
p_update(A[i], i - T.query(A[i] - 1));
}
for (int i = 0; i < Q; i++)
{
int src = A[X[i]];
if (src == V[i])
{
answer[i] = query(1, MAXN);
continue;
}
T.update(src, -1);
T.update(V[i], 1);
p_update(src, -1e7);
p_update(V[i], X[i] - T.query(V[i] - 1));
if (src < V[i])
{
if (src + 1 <= V[i] - 1)
update(src + 1, V[i] - 1, 1);
}
else
{
if (V[i] + 1 <= src - 1)
update(V[i] + 1, src - 1, -1);
}
A[X[i]] = V[i];
answer[i] = query(1, MAXN);
}
return answer;
}
