#include <bits/stdc++.h>
using namespace std;
#define lc ind<<1
#define rc ind<<1|1
const int MN = 1e6 + 5;
vector<pair<int,int>> xs; int sz;
int getx (const pair<int,int> &x) {return lower_bound(xs.begin(),xs.end(),x) - xs.begin() + 1;}
struct Node {
int mx,lz;
} tree[MN<<2];
void push_down (int ind, int l, int r) {
if (!tree[ind].lz) return;
tree[ind].mx += tree[ind].lz;
if (l!=r) {
tree[lc].lz += tree[ind].lz;
tree[rc].lz += tree[ind].lz;
}
tree[ind].lz = 0;
}
void update (int ind, int tl, int tr, int l, int r, int v) {
push_down(ind,tl,tr);
if (l > tr || r < tl) return;
if (l <= tl && tr <= r) {
tree[ind].lz += v;
push_down(ind,tl,tr);
return;
}
int mid = (tl + tr) / 2;
update(lc,tl,mid,l,r,v); update(rc,mid+1,tr,l,r,v);
tree[ind].mx = max(tree[lc].mx,tree[rc].mx);
}
int query (int ind, int tl, int tr, int l, int r) {
push_down(ind,tl,tr);
if (l > tr || r < tl) return INT_MIN;
if (l <= tl && tr <= r) return tree[ind].mx;
int mid = (tl + tr) / 2;
return max(query(lc,tl,mid,l,r),query(rc,mid+1,tr,l,r));
}
int bit[MN];
void u (int x, int v) {
for (;x<MN;x+=x&-x)
bit[x] += v;
}
int qu (int x) {
int ret = 0;
for (;x;x^=x&-x)
ret += bit[x];
return ret;
}
void s (int x, int v) {
int cur = query(1,1,sz,x,x);
update(1,1,sz,x,x,v - cur);
}
vector<int> countScans (vector<int> a, vector<int> x, vector<int> v) {
int n = a.size(), q = x.size(); vector<int> ret(q);
for (int i = 0; i < n; i++) xs.emplace_back(a[i],i);
for (int i = 0; i < q; i++) xs.emplace_back(v[i],x[i]);
sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
for (Node &nd : tree) nd = {-MN*1000,0};
sz = xs.size();
for (int i = 0; i < n; i++) u(getx({a[i],i}),1);
for (int i = 0; i < n; i++) {
int pos = getx({a[i],i});
s(pos,i - qu(pos-1));
}
for (int i = 0; i < q; i++) {
int oldpos = getx({a[x[i]],x[i]});
s(oldpos,-1e9);
if (oldpos + 1 <= sz) update(1,1,sz,oldpos+1,sz,1);
a[x[i]] = v[i];
int pos = getx({v[i],x[i]});
u(oldpos,-1); u(pos,1);
s(pos,x[i] - qu(pos-1));
if (pos + 1 <= sz) update(1,1,sz,pos+1,sz,-1);
ret[i] = query(1,1,sz,1,sz);
}
return ret;
}
