#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+6;
int n;
int a[MAXN];
int b[MAXN];
struct node
{
int val;
node *l, *r;
node(int x){
val=x;
l=nullptr;
r=nullptr;
}
node(node *_l,node *_r)
{
l=_l;
r=_r;
val=0;
if(l)val+=l->val;
if(r)val+=r->val;
}
node(node *t)
{
val=t->val;
l=t->l;
r=t->r;
}
};
node *update(node *t,int val,int pos,int l=1,int r=n)
{
//cerr<<"update "<<l<<" "<<r<<endl;
if(l==r)return new node(val);
int mid=(l+r)/2;
if(pos>mid)
{
if(t==nullptr)return new node(nullptr, update(nullptr,val,pos, mid+1,r));
else return new node(t->l, update(t->r,val,pos, mid+1,r));
}
else
{
if(t==nullptr)return new node(update(nullptr,val,pos,l,mid), nullptr);
else return new node(update(t->l,val,pos,l,mid), t->r);
}
}
int query(node *t,int ql,int qr,int l=1,int r=n)
{
//cerr<<"query "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
if(ql>r)return 0;
if(t==nullptr)return 0;
if(qr<l)return 0;
if(l>=ql&&r<=qr)return t->val;
int mid=(l+r)/2;
return query(t->l,ql,qr,l,mid)+query(t->r,ql,qr,mid+1,r);
}
node *roots[MAXN];
struct segment
{
int l,r;
};
vector<segment>v;
bool cmp(segment s1,segment s2)
{
if(s1.r!=s2.r)return s1.r<s2.r;
else return s1.l<s2.l;
}
vector<segment>s1[MAXN];
int sum[MAXN];
void init(int N, int A[], int B[]) {
n=N;
for(int i=0;i<N;i++)
{
a[i]=A[i];
b[i]=B[i];
v.push_back({A[i],B[i]});
}
sort(v.rbegin(),v.rend(),cmp);
for(auto xd:v)
{
s1[xd.r].push_back(xd);
}
roots[n+1]=nullptr;
for(int i=n;i>=1;i--)
{
roots[i]=roots[i+1];
//cout<<"???\n";
{
for(auto xd:s1[i])
{
++sum[xd.l];
roots[i]=update(roots[i],sum[xd.l],xd.l,1,n);
//cerr<<" "<<xd.l<<" ^^"<<endl;
}
}
}
}
int m;
int k[MAXN];
int dp[MAXN];
int get_value1(int x)
{
node* root_we_need = roots[x];
return query(root_we_need,1,x,1,n);
}
int get_value(int i1,int i2)
{
if(k[i1]+1>k[i2])return 0;
//should return no. of segments with k[i2]>=l>k[i1] and r>=k[i2]
//persistent segment tree can do :(
node *root_we_need = roots[k[i2]];
return query(root_we_need, k[i1]+1,k[i2],1,n);
}
int can(int M, int K[]) {
//cerr<<"========query=========";
sort(K,K+M);
int sumk=0;
for(int i=0;i<M;i++)
{
k[i]=K[i];
sumk+=k[i];
}
if(sumk>n)return 0;
m=M;
dp[0]=get_value1(K[0])-K[0];
if(dp[0]<0)return 0;
vector<int>ids;
ids.push_back(0);
//cerr<<"0 : "<<dp[0]<<endl;
for(int i=1;i<m;i++)
{
while(ids.size()>1)
{
int id1=ids[ids.size()-2];
int id2=ids[ids.size()-1];
if(get_value(id1, i)+dp[id1]<=get_value(id2, i)+dp[id2])
{
ids.pop_back();
}
else
{
break;
}
}
dp[i]=dp[ids.back()]+get_value(ids.back(), i)-K[i];
//cerr<<i<<" : "<<dp[i]<<endl;
if(dp[i]<0)return 0;
ids.push_back(i);
}
return 1;
}
