#include <bits/stdc++.h>
using namespace std;
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V);
typedef long long ll;
const int maxn=5e5+7;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=1e9+7;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
//#define int ll
#ifdef HNO2
#define IOS
#else
#include <bubblesort2.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#endif // HNO2
vector<ll> values;
ll a[maxn];
ll x[maxn],v[maxn];
const int C=1e8;
struct segtree
{
int seg[maxn*2*4],tag[maxn*2*4];
void init()
{
memset(seg,0,sizeof(seg));
memset(tag,0,sizeof(tag));
}
void push(int now,int l,int r)
{
if (l==r||tag[now]==0)
{
tag[now]=0;
return;
}
seg[now*2]+=tag[now];
tag[now*2]+=tag[now];
seg[now*2+1]+=tag[now];
tag[now*2+1]+=tag[now];
tag[now]=0;
}
void modify(int now,int l,int r,int ql,int qr,int vv)
{
if (l>=ql&&r<=qr)
{
seg[now]+=vv;
tag[now]+=vv;
return;
}
int m=(l+r)>>1;
push(now,l,r);
if (ql<=m) modify(now*2,l,m,ql,qr,vv);
if (qr>m) modify(now*2+1,m+1,r,ql,qr,vv);
seg[now]=max(seg[now*2],seg[now*2+1]);
}
int query()
{
return seg[1];
}
}tree;
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int n=sz(A),q=sz(X);
vector<int> ans;
for (int i=1;i<=n;i++) a[i]=A[i-1]*1ll*C+i,values.pb(A[i-1]*1ll*C+i);
for (int i=1;i<=q;i++)
{
x[i]=X[i-1]+1;
v[i]=V[i-1]*1ll*C+(X[i-1]+1);
values.pb(V[i-1]*1ll*C+(X[i-1]+1));
}
//values.pb(-1);
sort(all(values));
values.resize(unique(all(values))-values.begin());
for (int i=1;i<=n;i++) a[i]=lower_bound(all(values),a[i])-values.begin()+1;
for (int i=1;i<=q;i++) v[i]=lower_bound(all(values),v[i])-values.begin()+1;
int N=sz(values);
tree.init();
for (int i=1;i<=N;i++) tree.modify(1,1,N,i,i,-C+(values[i-1]%C));
for (int i=1;i<=n;i++)
{
tree.modify(1,1,N,a[i],a[i],C);
if (a[i]!=N) tree.modify(1,1,N,a[i]+1,N,-1);
}
for (int i=1;i<=q;i++)
{
if (a[x[i]]!=N) tree.modify(1,1,N,a[x[i]]+1,N,1);
tree.modify(1,1,N,a[x[i]],a[x[i]],-C);
a[x[i]]=v[i];
if (a[x[i]]!=N) tree.modify(1,1,N,a[x[i]]+1,N,-1);
tree.modify(1,1,N,a[x[i]],a[x[i]],C);
ans.pb(tree.query()-1);
}
return ans;
}
