#include<bits/stdc++.h>
#include "bubblesort2.h"
#define ll long long
using namespace std;
int val[1000005],aint[4000005],lazy[4000005];
vector<pair<int,int>>aux;
int n,q,l;
void push(int nod,int st,int dr)
{
if (lazy[nod]){
aint[nod]+=lazy[nod];
if (st!=dr){
lazy[nod*2]+=lazy[nod];
lazy[nod*2+1]+=lazy[nod];
}
lazy[nod]=0;
}
}
void update(int nod,int st,int dr,int l,int r,int add)
{
if (l>r)
return ;
if (l<=st && dr<=r){
aint[nod]+=add;
if (st!=dr){
lazy[nod*2]+=add;
lazy[nod*2+1]+=add;
}
return ;
}
push(nod,st,dr);
int mij=(st+dr)/2;
if (l<=mij)
update(nod*2,st,mij,l,r,add);
if (mij+1<=r)
update(nod*2+1,mij+1,dr,l,r,add);
push(nod*2,st,mij);
push(nod*2+1,mij+1,dr);
aint[nod]=max(aint[nod*2],aint[nod*2+1]);
}
void update2(int nod,int st,int dr,int poz,int val)
{
if (st==dr){
aint[nod]+=val;
return ;
}
push(nod,st,dr);
int mij=(st+dr)/2;
if (poz<=mij)
update2(nod*2,st,mij,poz,val);
else
update2(nod*2+1,mij+1,dr,poz,val);
push(nod*2,st,mij);
push(nod*2+1,mij+1,dr);
aint[nod]=max(aint[nod*2],aint[nod*2+1]);
}
int calcpoz(pair<int,int>auxi)
{
return lower_bound(aux.begin(),aux.end(),auxi)-aux.begin();
}
vector<int> countScans(vector<int>a,vector<int>x,vector<int>v)
{
n=a.size();
q=x.size();
int i;
for(i=0;i<n;i++)
aux.push_back(make_pair(a[i],i));
for(i=0;i<q;i++)
aux.push_back(make_pair(v[i],x[i]));
sort(aux.begin(),aux.end());
aux.resize(unique(aux.begin(),aux.end())-aux.begin());
for(i=0;i<n;i++){
int ind1=calcpoz(make_pair(a[i],i));
update(1,0,aux.size()-1,ind1,ind1,(i+1));
int ind2=calcpoz(make_pair(a[i],-1));
update(1,0,aux.size()-1,ind2,aux.size()-1,-1);
}
vector<int>ans;
for(i=0;i<q;i++){
int ind1=calcpoz(make_pair(a[x[i]],x[i]));
update(1,0,aux.size()-1,ind1,ind1,-(x[i]+1));
int ind2=calcpoz(make_pair(a[x[i]],-1));
update(1,0,aux.size()-1,ind2,aux.size()-1,1);
a[x[i]]=v[i];
ind1=calcpoz(make_pair(a[x[i]],x[i]));
update(1,0,aux.size()-1,ind1,ind1,(x[i]+1));
ind2=calcpoz(make_pair(a[x[i]],-1));
update(1,0,aux.size()-1,ind2,aux.size()-1,-1);
ans.push_back(aint[1]);
}
return ans;
}
