#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cout << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__);
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 5e5 + 10;
int n, q, sz, seg[maxn << 3], lazy[maxn << 3];
vector<int> num;
set<int> idx[maxn << 1];
void shift(int v, int l, int r);
void add(int v, int l, int r, int ql, int qr, int val){
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
seg[v] += val;
lazy[v] += val;
return;
}
shift(v, l, r);
int mid = (l + r)>> 1;
add(v << 1, l, mid, ql, qr, val);
add(v << 1 | 1, mid, r, ql, qr, val);
seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
}
void shift(int v, int l, int r){
if (lazy[v] == 0) return;
int mid = (l+r) >> 1;
add(v << 1, l, mid, l, mid, lazy[v]);
add(v << 1 | 1, mid, r, mid, r, lazy[v]);
lazy[v] = 0;
}
void add(int x, int y){
auto it = idx[y].end();
it--;
if (x > *it) add(1, 0, sz, y, y+1, x-(*it));
add(1, 0, sz, y, sz, -1);
idx[y].insert(x);
}
void remove(int x, int y){
idx[y].erase(x);
add(1, 0, sz, y, sz, 1);
auto it = idx[y].end();
it--;
if (x > *it) add(1, 0, sz, y, y+1, -x+(*it));
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
n = A.size();
q = X.size();
for (int i = 0; i < n; i++) num.push_back(A[i]);
for (int i = 0; i < q; i++) num.push_back(V[i]);
sort(all(num));
num.resize(distance(num.begin(), unique(all(num))));
sz = num.size();
for (int i = 0; i < sz; i++) idx[i].insert(0);
for (int i = 0; i < n; i++){
A[i] = lower_bound(all(num), A[i]) - num.begin();
add(i+1, A[i]);
}
vector<int> ans;
for (int i = 0; i < q; i++){
V[i] = lower_bound(all(num), V[i]) - num.begin();
remove(X[i]+1, A[X[i]]);
A[X[i]] = V[i];
add(X[i]+1, A[X[i]]);
ans.push_back(max(0, seg[1]));
}
return ans;
}
