/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
*/
#pragma GCC target("sse4,tune=native")
#pragma GCC optimize("O3","unroll-loops")
#include "bubblesort2.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <iomanip>
#include <deque>
using namespace std;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define x first
#define y second
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
const string FILENAME = "input";
const int MAXN = 500228;
const int block = 750;
int n;
int id[MAXN * 2];
int who[MAXN * 2];
vector<pair<int, int> > st[MAXN];
vector<int> mod[MAXN];
vector<int> d[MAXN];
int ss[MAXN];
int pos[MAXN * 2];
inline void push(const int &i, const int &v) {
if (mod[i][v]) {
d[i][v] += mod[i][v];
if (v < ss[i]) {
mod[i][v << 1] += mod[i][v];
mod[i][(v << 1) + 1] += mod[i][v];
}
mod[i][v] = 0;
}
}
void add(const int &i, int v, int vl, int vr, const int &l, const int &r, const int &x) {
if (vl > r || vr < l) {
push(i, v);
return;
}
if (l <= vl && vr <= r) {
mod[i][v] += x;
push(i, v);
return;
}
push(i, v);
int vn = v << 1;
int vm = (vl + vr) >> 1;
add(i, vn, vl, vm, l, r, x);
add(i, vn + 1, vm + 1, vr, l, r, x);
d[i][v] = max(d[i][vn], d[i][vn + 1]);
}
bool need = false;
void add(int i) {
int cnt = 1000000000;
for (int j = i - 1; j >= i - (i % block); j--) {
if (who[id[j]] > who[id[i]]) {
cnt++;
}
}
int ids = i / block;
add((ids), 1, 1, ss[(ids)], pos[id[i]], pos[id[i]], cnt);
for (int j = (ids) + 1; j <= (n - 1) / block; j++) {
int t = lower_bound(all(st[j]), make_pair(who[id[i]], 0)) - st[j].begin();
if (t) {
add(j, 1, 1, ss[j], 1, t, 1);
}
}
}
int res[MAXN * 2];
void deladd(int i, int nid) {
int ids = i / block;
int bmax = min(i - (i % block) + block - 1, n - 1);
for (int j = 1; j < 2 * ss[ids]; j++) {
push(ids, j);
}
for (int j = 0; j < sz(st[ids]); j++) {
res[st[ids][j].second] = d[ids][ss[ids] + j];
}
st[ids].pb({who[nid], nid});
int cur = sz(st[ids]) - 1;
while (cur && st[ids][cur] < st[ids][cur - 1]) {
swap(st[ids][cur], st[ids][cur - 1]);
cur--;
}
for (int j = i + 1; j <= bmax; j++) {
int cnt = 0;
if (who[id[j]] < who[id[i]]) {
cnt--;
}
if (who[id[j]] < who[nid]) {
cnt++;
}
if (cnt != 0) {
res[id[j]] += cnt;
}
}
int cnt = 0;
for (int j = i - 1; j >= i - (i % block); j--) {
if (who[id[j]] > who[nid]) {
cnt++;
}
}
res[nid] = cnt;
for (int j = (ids) - 1; j >= 0; j--) {
int t = upper_bound(all(st[j]), make_pair(who[nid], 1000000000)) - st[j].begin();
res[nid] += sz(st[j]) - t;
}
int pos = 0;
for (int j = 0; j < sz(st[ids]); j++) {
if (st[ids][j].second == id[i]) {
swap(st[ids][j], st[ids].back());
pos = j;
break;
}
}
st[ids].pop_back();
while (pos < sz(st[ids]) - 1) {
swap(st[ids][pos], st[ids][pos + 1]);
pos++;
}
for (int j = 0; j < sz(st[ids]); j++) {
d[ids][ss[ids] + j] = res[st[ids][j].second];
mod[ids][ss[ids] + j] = 0;
}
for (int j = ss[ids] - 1; j >= 1; j--) {
d[ids][j] = max(d[ids][j * 2], d[ids][j * 2 + 1]);
mod[ids][j] = 0;
}
for (int j = (ids) + 1; j <= (n - 1) / block; j++) {
int t = lower_bound(all(st[j]), make_pair(who[id[i]], 0)) - st[j].begin();
int t1 = lower_bound(all(st[j]), make_pair(who[nid], 0)) - st[j].begin();
//1 - t === -1
//1 - t1 == +1;
if (t != t1) {
if (t == 0 && t1 != 0) {
add(j, 1, 1, ss[j], 1, t1, 1);
} else if (t1 == 0 && t != 0) {
add(j, 1, 1, ss[j], 1, t, -1);
} else {
if (t < t1) {
add(j, 1, 1, ss[j], t + 1, t1, 1);
} else {
add(j, 1, 1, ss[j], t1 + 1, t, -1);
}
}
}
}
}
std::vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
n = sz(A);
for (int i = 0; i < n; i++) {
st[(i / block)].pb({A[i], i});
id[i] = i;
who[i] = A[i];
}
vector<int> answer;
for (int i = 0; i <= (n - 1) / block; i++) {
sort(all(st[i]));
ss[i] = 1;
while (ss[i] < sz(st[i])) {
ss[i] <<= 1;
}
d[i].resize(2 * ss[i]);
mod[i].resize(2 * ss[i]);
for (int j = 0; j < sz(st[i]); j++) {
pos[st[i][j].second] = j + 1;
}
for (int j = 0; j < 2 * ss[i]; j++) {
d[i][j] = -1e9;
mod[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
add(i);
}
need = true;
//exit(0);
for (int i = 0; i < sz(X); i++) {
who[n + i] = V[i];
deladd(X[i], n + i);
id[X[i]] = n + i;
int res = 0;
for (int j = 0; j <= (n - 1) / block; j++) {
chkmax(res, d[j][1] + mod[j][1]);
}
answer.pb(res);
}
return answer;
}
