#include <bits/stdc++.h>
#include "teams.h"
#define pii pair<int,int>
#define x first
#define y second
#define MAXN 500005
using namespace std;
int L[MAXN],R[MAXN],n,root[MAXN];
struct Node{
int l,r,lch,rch,val;
Node(int _l=0,int _r=0,int a=0,int b=0,int c=0):l(_l),r(_r),lch(a),rch(b),val(c){}
};
struct segtree{
vector<Node>seg;
int num=0;
int add_node(int l,int r){
seg.push_back(Node(l,r,0,0,0));
return num++;
}
void build(int i){
int l=seg[i].l,r=seg[i].r,mid=(l+r)>>1;
if (l==r) return;
seg[i].lch=add_node(l,mid);
seg[i].rch=add_node(mid+1,r);
build(seg[i].lch); build(seg[i].rch);
}
void Insert(int i,int j,int p,int c){
int l=seg[i].l,r=seg[i].r,mid=(l+r)>>1;
if (l==r){
seg[i].val+=c;
return;
}
if (p<=mid){
seg[i].lch=add_node(l,mid); seg[i].rch=seg[j].rch;
seg[seg[i].lch]=seg[seg[j].lch];
Insert(seg[i].lch,seg[j].lch,p,c);
seg[i].val=seg[seg[i].lch].val+seg[seg[i].rch].val;
}
else {
seg[i].rch=add_node(mid+1,r); seg[i].lch=seg[j].lch;
seg[seg[i].rch]=seg[seg[j].rch];
Insert(seg[i].rch,seg[j].rch,p,c);
seg[i].val=seg[seg[i].rch].val+seg[seg[i].lch].val;
}
}
int query(int i,int j,int ll,int rr){
// 計算 版本 i~j ll~rr 點的個數
// 也就是 L1~L2 ll<=R<=rr 的點的個數
int l=seg[i].l,r=seg[i].r,mid=(l+r)>>1;
if (ll>rr) return 0;
if (ll<=l&&rr>=r)
return seg[i].val-seg[j].val;
if (rr<=mid) return query(seg[i].lch,seg[j].lch,ll,rr);
else if (ll>mid) return query(seg[i].rch,seg[j].rch,ll,rr);
else return query(seg[i].lch,seg[j].lch,ll,mid)+query(seg[i].rch,seg[j].rch,mid+1,rr);
}
int query_pos(int i,int j,int need){
int l=seg[i].l,r=seg[i].r;
if (l==r) return l;
int tmp=seg[seg[i].lch].val-seg[seg[j].lch].val;
if (tmp<need) return query_pos(seg[i].rch,seg[j].rch,need-tmp);
else return query_pos(seg[i].lch,seg[j].lch,need);
}
void debug(int i){
cout<<seg[i].l<<" "<<seg[i].r<<" -> "<<seg[i].val<<'\n';
if (seg[i].l==seg[i].r)
return;
debug(seg[i].lch); debug(seg[i].rch);
}
}seg;
void init(int N, int A[], int B[]) {
n=N;
vector<pii>all;
for (int i=1;i<=n;i++){
L[i]=A[i-1]; R[i]=B[i-1];
all.push_back({L[i],R[i]});
}
sort(all.begin(),all.end());
root[0]=seg.add_node(1,n+1);
seg.build(0);
for (int i=1,j=0;i<=n;i++){
root[i]=root[i-1];
while (j<n&&all[j].x==i){
int nrt=seg.add_node(1,n+1);
seg.Insert(nrt,root[i],all[j].y,1);
root[i]=nrt; j++;
}
}
}
int H[MAXN],last[MAXN],K[MAXN];
int can(int M, int NK[]) {
for (int i=0;i<=M+5;i++){
last[i]=0; H[i]=0; K[i]=0;
}
H[0]=n+1;
for (int i=1;i<=M;i++)
K[i]=NK[i-1];
sort(K+1,K+1+M);
vector<int>st;
for (int i=1;i<=M;i++){
while (!st.empty()&&H[st.back()]<K[i]) st.pop_back();
int need=K[i]; last[i]=0; H[i]=K[i]-1;
if (K[i]>n) return 0;
while (!st.empty()){
int j=st.back();
int h=H[j];
if (K[i]==K[j]){
H[i]=H[j]; last[i]=last[j];
st.pop_back();
continue;
}
int get=seg.query(root[K[i]],root[K[j]],H[i]+1,h)+last[j]+last[i];
if (get<need){
need-=get; H[i]=h; last[i]=0;
st.pop_back();
}
else break;
}
int j=(st.empty()) ? 0 : st.back();
int out=seg.query(root[K[i]],root[K[j]],1,H[i]);
int l=seg.query_pos(root[K[i]],root[K[j]],out+need-last[i]);
l=min(l,H[j]);
// cout<<j<<" -> "<<out<<" "<<need<<" "<<last[i]<<'\n';
/*
int l=H[i],r=H[j];
while (l<r){
int mid=(l+r)>>1;
int val=seg.query(root[K[i]],root[K[j]],H[i]+1,mid)+last[i];
if (val>=need) r=mid;
else l=mid+1;
}
*/
int can_use=seg.query(root[K[i]],root[K[j]],H[i]+1,l)+last[i];
H[i]=l;
while (!st.empty()&&H[i]==H[st.back()]){
can_use+=last[st.back()];
st.pop_back();
}
last[i]=can_use-need;
// cout<<i<<" "<<K[i]<<" : "<<H[i]<<' '<<last[i]<<'\n';
if (can_use<need)
return 0;
st.push_back(i);
}
return 1;
}
