#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
long long n,as[500069],fw[500069],fi,inf=1e18;
void ud(long long x,long long w)
{
for(fi=x;fi<=n;fi+=fi&-fi)
{
fw[fi]+=w;
}
}
long long qr(long long lh,long long rh)
{
long long z=0;
for(fi=rh;fi;fi-=fi&-fi)
{
z+=fw[fi];
}
for(fi=lh-1;fi;fi-=fi&-fi)
{
z-=fw[fi];
}
return z;
}
vector<int> countScans(vector<int> a,vector<int> qp,vector<int> qw)
{
long long t=qp.size(),rr,i,k,z;
vector<int> sq;
n=a.size();
for(rr=0;rr<t;rr++)
{
a[qp[rr]]=qw[rr];
for(i=0;i<n;i++)
{
as[i]=a[i];
fw[i+1]=0;
}
sort(as,as+n);
z=-inf;
for(i=0;i<n;i++)
{
k=lower_bound(as,as+n,a[i])-as+1;
z=max(z,qr(k+1,n));
ud(k,1);
}
sq.push_back(z);
}
return sq;
}
