#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
int n,nsg=0,nn,fq[500069],la[10000069],ra[10000069],sma[10000069],pa[10000069][2],sg[500069],inf=1e9;
pair<int,int> a[2][500069],sk[200069];
void bd(int ix,int lh,int rh)
{
la[ix]=lh;
ra[ix]=rh;
sma[ix]=0;
if(la[ix]!=ra[ix])
{
int ii,md=(la[ix]+ra[ix])/2;
for(ii=0;ii<2;ii++)
{
nsg++;
pa[ix][ii]=nsg;
bd(nsg,!ii?la[ix]:md+1,!ii?md:ra[ix]);
}
}
}
void ud(int ix,int x,int w)
{
if(la[ix]>=x&&ra[ix]<=x)
{
sma[ix]+=w;
}
else
{
int ii,jj,p;
for(ii=0;ii<2;ii++)
{
p=pa[ix][ii];
if(la[p]<=x&&ra[p]>=x)
{
nsg++;
la[nsg]=la[p];
ra[nsg]=ra[p];
sma[nsg]=sma[p];
for(jj=0;jj<2;jj++)
{
pa[nsg][jj]=pa[p][jj];
}
pa[ix][ii]=nsg;
ud(nsg,x,w);
}
}
sma[ix]=sma[pa[ix][0]]+sma[pa[ix][1]];
}
}
int qr(int ix,int lh,int rh,int sr)
{
if(la[ix]>rh||ra[ix]<lh)
{
return 0;
}
else if(la[ix]>=lh&&ra[ix]<=rh)
{
return sma[ix]-sma[sr];
}
else
{
return qr(pa[ix][0],lh,rh,pa[sr][0])+qr(pa[ix][1],lh,rh,pa[sr][1]);
}
}
int bl(int ix,int x,int sr)
{
if(la[ix]==ra[ix])
{
return la[ix];
}
else
{
int ii,p,p2;
for(ii=0;ii<2;ii++)
{
p=pa[ix][ii];
p2=pa[sr][ii];
if(x<=sma[p]-sma[p2])
{
return bl(p,x,p2);
}
x-=sma[p]-sma[p2];
}
return -1;
}
}
void init(int on,int laa[],int raa[])
{
int i,ii,k,l;
n=on;
for(i=1;i<=n;i++)
{
k=laa[i-1];
l=raa[i-1];
a[0][i]={k,l};
}
sort(a[0]+1,a[0]+n+1);
for(i=1;i<=n;i++)
{
l=a[0][i].sc;
fq[l]++;
a[1][i]={l,fq[l]};
}
sort(a[1]+1,a[1]+n+1);
for(i=n;i;i--)
{
l=a[0][i].sc;
a[0][i].sc=lower_bound(a[1]+1,a[1]+n+1,mp(l,fq[l]))-a[1];
fq[l]--;
}
nsg++;
sg[0]=nsg;
bd(nsg,1,n);
for(i=1;i<=n;i++)
{
l=a[0][i].sc;
nsg++;
la[nsg]=la[sg[i-1]];
ra[nsg]=ra[sg[i-1]];
sma[nsg]=sma[sg[i-1]];
for(ii=0;ii<2;ii++)
{
pa[nsg][ii]=pa[sg[i-1]][ii];
}
sg[i]=nsg;
ud(nsg,l,1);
}
}
int can(int sz,int qq[])
{
int i,k,l,w,sm;
sort(qq,qq+sz);
nn=0;
for(i=0;i<sz;i++)
{
sm=qq[i];
k=upper_bound(a[0]+1,a[0]+n+1,mp(sm,inf))-a[0]-1;
l=lower_bound(a[1]+1,a[1]+n+1,mp(sm,0))-a[1]-1;
for(;nn;nn--)
{
w=qr(sg[k],l+1,sk[nn].sc-1,sg[sk[nn].fr]);
if(w>sm)
{
break;
}
l=max(l,sk[nn].sc);
sm-=w;
}
l=bl(sg[k],qr(sg[k],1,l,sg[sk[nn].fr])+sm,sg[sk[nn].fr]);
if(l==-1)
{
return 0;
}
nn++;
sk[nn]={k,l};
}
return 1;
}
