#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10,lg=20,kaf=(1<<lg),maxq=maxn;
vector<pair<int,int>>alle;
int n,dproot[maxn],root,m;
vector<int>ezaf[maxn];
vector<int>all;
vector<pair<int,int>>unnow;
struct segment{
struct node{
int cl,cr,w;
node(){
w=0;
cl=cr=0;
}
};
node seg[maxq*lg];
int te=1;
vector<int>hey,hey2;
int upd(int i,int l,int r,int tl,int tr,int w){
while(true){
int u=te;
seg[te]=seg[i];
te++;
if(l>=tl&&r<=tr){
seg[u].w+=w;
int last=u;
while((int)hey.size()>0){
if(hey2.back()==0){
seg[hey.back()].cl=last;
}else{
seg[hey.back()].cr=last;
}
last=hey.back();
seg[last].w=seg[seg[last].cl].w+seg[seg[last].cr].w;
hey.pop_back();
hey2.pop_back();
}
return last;
}
int mid=(l+r)>>1;
if(tl<=mid){
hey.push_back(u);
hey2.push_back(0);
u=seg[u].cl;
r=mid;
//seg[u].cl=upd(seg[u].cl,l,mid,tl,tr,w);
}else{
hey.push_back(u);
hey2.push_back(1);
u=seg[u].cr;
l=mid+1;
//seg[u].cr=upd(seg[u].cr,mid+1,r,tl,tr,w);
}
//seg[u].w=seg[seg[u].cl].w+seg[seg[u].cr].w;
}
return 0;
}
int pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return 0;
}
if(l>=tl&&r<=tr){
return seg[i].w;
}
int mid=(l+r)>>1;
return pors(seg[i].cl,l,mid,tl,tr)+pors(seg[i].cr,mid+1,r,tl,tr);
}
}seg;
vector<pair<int,int>>tof;
void init(int N, int A[], int B[]) {
n=N;
set<pair<int,int>>st;
tof.push_back(make_pair(0,0));
for(int i=0;i<n;i++){
tof.push_back(make_pair(A[i],i));
tof.push_back(make_pair(B[i],i+n));
}
sort(tof.begin(),tof.end());
for(int i=0;i<(int)tof.size();i++){
if(tof[i].second<n){
A[tof[i].second]=i;
}else{
B[tof[i].second-n]=i;
}
}
for(int i=0;i<n;i++){
// cout<<"hey: "<<A[i]<<" "<<B[i]<<" "<<i<<endl;
alle.push_back(make_pair(A[i],B[i]));
ezaf[alle[i].second].push_back(alle[i].first);
st.insert(alle.back());
}
for(int i=1;i<maxn;i++){
for(auto x:ezaf[i]){
root=seg.upd(root,0,kaf-1,x,x,1);
}
dproot[i]=root;
}
}
int upd(int w,int ind,int mn=0){
if((int)unnow.size()==0){
return 0;
}
int z=seg.pors(dproot[unnow.back().second],0,kaf-1,unnow.back().first,ind)-seg.pors(dproot[mn],0,kaf-1,unnow.back().first,ind);
//cout<<w<<" "<<ind<<" "<<mn<<" "<<z<<" "<<unnow.back().first<<" "<<unnow.back().second<<" "<<seg.pors(dproot[unnow.back().second],0,kaf-1,unnow.back().first,ind)<<" "<<seg.pors(dproot[mn],0,kaf-1,unnow.back().first,ind)<<endl;
if(unnow.back().second<=mn){
unnow.pop_back();
return upd(w,ind,mn);
}
if(z<w){
w-=z;
int f=unnow.back().second;
unnow.pop_back();
return upd(w,ind,max(f,mn));
}
int low=mn,high=unnow.back().second+1,mid;
while(high-low>1){
mid=(high+low)>>1;
z=seg.pors(dproot[mid],0,kaf-1,unnow.back().first,ind)-seg.pors(dproot[mn],0,kaf-1,unnow.back().first,ind);
if(z>w){
high=mid;
}else{
low=mid;
}
}
int ez=low;
low=unnow.back().first,high=ind+1;
while(high-low>1){
mid=(high+low)>>1;
z=seg.pors(dproot[ez],0,kaf-1,unnow.back().first,mid)+seg.pors(dproot[ez-1],0,kaf-1,mid+1,ind)-seg.pors(dproot[mn],0,kaf-1,unnow.back().first,ind);
if(z>w){
high=mid;
}else{
low=mid;
}
}
unnow.push_back(make_pair(low+1,ez));
if(low!=ind){
unnow.push_back(make_pair(ind+1,ez-1));
}
return 1;
}
int can(int M, int K[]) {
m=M;
all.clear();
for(int i=0;i<m;i++){
all.push_back(K[i]);
}
sort(all.begin(),all.end());
unnow.clear();
unnow.push_back(make_pair(0,(int)tof.size()+1));
for(int i=0;i<m;i++){
int indl=(int)(lower_bound(tof.begin(),tof.end(),make_pair(all[i],-1))-tof.begin()),indr=(int)(lower_bound(tof.begin(),tof.end(),make_pair(all[i]+1,-1))-tof.begin())-1;
//cout<<indl<<" "<<indr<<" "<<all[i]<<endl;
unnow.push_back(make_pair(indr+1,indl-1));
if(upd(all[i],indr,0)==0){
return 0;
}
}
return 1;
}
