#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int INF = int(1e9);
struct node
{
int mn,lazy;
};
node st[4222222];
void push(int id, int l, int r)
{
if(st[id].lazy!=0)
{
st[id].mn+=st[id].lazy;
if(r-l>=2)
{
st[id*2].lazy+=st[id].lazy;
st[id*2+1].lazy+=st[id].lazy;
}
st[id].lazy=0;
}
}
void combine(int id)
{
st[id].mn=min(st[id*2].mn,st[id*2+1].mn);
}
void build(int id, int l, int r)
{
if(r-l<2)
{
st[id].lazy=0;
st[id].mn=INF;
return ;
}
int mid=(l+r)>>1;
build(id*2,l,mid); build(id*2+1,mid,r);
combine(id);
}
void add(int id, int l, int r, int ql, int qr, int v)
{
push(id,l,r);
if(ql>=r||l>=qr) return ;
if(ql<=l&&r<=qr)
{
st[id].lazy+=v;
push(id,l,r);
return ;
}
int mid=(l+r)>>1;
add(id*2,l,mid,ql,qr,v); add(id*2+1,mid,r,ql,qr,v);
combine(id);
}
void update(int id, int l, int r, int pos, int v)
{
push(id,l,r);
if(pos>=r||pos<l) return ;
if(r-l<2)
{
st[id].lazy=0; st[id].mn=v;
return ;
}
int mid=(l+r)>>1;
update(id*2,l,mid,pos,v); update(id*2+1,mid,r,pos,v);
combine(id);
}
int query(int id, int l, int r, int ql, int qr)
{
push(id,l,r);
if(ql>=r||l>=qr) return INF;
if(ql<=l&&r<=qr) return st[id].mn;
int mid=(l+r)>>1;
return min(query(id*2,l,mid,ql,qr),query(id*2+1,mid,r,ql,qr));
}
pbds T;
int ma[511111];
int maq[511111];
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V)
{
int Q=X.size();
std::vector<int> answer(Q);
int n = A.size(); T.clear();
int timer=0;
for(int i=0;i<n;i++) T.insert(mp(A[i],++timer));
vector<pair<int,ii> > vec;
for(int i=0;i<n;i++) vec.pb(mp(A[i],mp(i,-1)));
for(int i=0;i<Q;i++) vec.pb(mp(V[i],mp(X[i],i)));
sort(vec.begin(),vec.end());
int N = n+Q;
for(int i=0;i<N;i++)
{
if(vec[i].se.se==-1)
{
ma[vec[i].se.fi] = i;
}
}
for(int i=0;i<N;i++)
{
if(vec[i].se.se>=0)
{
maq[vec[i].se.se] = i;
}
}
for(int i=0;i<n;i++)
{
update(1,0,N,ma[i],-(i+1)+T.order_of_key(mp(A[i]+1,-2)));
//cerr<<"P : "<<i<<' '<<(i+1)-T.order_of_key(mp(A[i]+1,-2))<<'\n';
}
for(int i=0;i<Q;i++)
{
auto it = T.lower_bound(mp(A[X[i]],-1)); T.erase(it); T.insert(mp(V[i],++timer));
update(1,0,N,ma[X[i]],INF);
ma[X[i]] = maq[i];
//remove A[X[i]] from memories
//add V[i] to memories
int lb = lower_bound(vec.begin(),vec.end(),mp(A[X[i]],mp(-2,-2))) - vec.begin();
add(1,0,N,lb,N,-1);
lb = lower_bound(vec.begin(),vec.end(),mp(V[i],mp(-2,-2))) - vec.begin();
add(1,0,N,lb,N,1);
update(1,0,N,ma[X[i]],-(X[i]+1)+int(T.order_of_key(mp(V[i]+1,-2))));
//cerr<<"SPECIAL : "<<-(X[i]+1)+int(T.order_of_key(mp(V[i]+1,-2)))<<'\n';
answer[i] = -query(1,0,N,0,N);
A[X[i]] = V[i];
}
return answer;
}
