#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct Node{
vector<int> data;
void merge(const Node &tl, const Node &tr){
data.resize(tl.data.size()+tr.data.size());
std::merge(tl.data.begin(), tl.data.end(), tr.data.begin(), tr.data.end(), data.begin());
}
};
struct SegmentTree{
int n;
vector<Node> t;
void init(int _n){
n=_n;
t.assign(4*n+1, Node());
}
void build(int k, int l, int r, pair<int, int> a[]){
if (l==r){
t[k].data.push_back(a[l].second);
return;
}
int mid=(l+r)>>1;
build(k<<1, l, mid, a);
build(k<<1|1, mid+1, r, a);
t[k].merge(t[k<<1], t[k<<1|1]);
}
// int cnt;
// int count(int k, int val){
// return upper_bound(t[k].data.begin(), t[k].data.end(), val)-t[k].data.begin();
// }
int get(int k, int l, int r, int L, int R, int val){
if (r<L || R<l) return 0;
if (L<=l && r<=R) return t[k].data.end()-lower_bound(t[k].data.begin(), t[k].data.end(), val);
int mid=(l+r)>>1;
return get(k<<1, l, mid, L, R, val)+get(k<<1|1, mid+1, r, L, R, val);
}
// int walk(int k, int l, int r, int L, int R, int val){
// if (r<L || R<l) return 0;
// if (L<=l && r<=R){
// int cc=count(k, val);
// if (cc<cnt){
// cnt-=cc;
// return 0;
// }
// }
// if (l==r) return t[k].data[0]<=val && cnt==1;
// int mid=(l+r)>>1;
// int ans=walk(k<<1, l, mid, L, R, val);
// if (ans) return ans;
// return walk(k<<1|1, mid+1, r, L, R, val);
// }
} st;
const int N=5e5+10;
int n, pos[N];
pair<int, int> a[N];
void init(int _N, int _A[], int _B[]) {
n=_N;
for (int i=1; i<=n; ++i) a[i]={_A[i-1], _B[i-1]};
sort(a+1, a+n+1);
st.init(n);
st.build(1, 1, n, a);
for (int i=1; i<=n; ++i) pos[i]=0;
for (int i=1; i<=n; ++i) pos[a[i].first]=max(pos[a[i].first], i);
for (int i=2; i<=n; ++i) pos[i]=max(pos[i], pos[i-1]);
}
int can(int M, int K[]) {
sort(K, K+M);
for (int i=0; i<M; ++i){
int sum=0;
for (int j=i; j<M; ++j){
sum+=K[j];
if (st.get(1, 1, n, 1, pos[K[j]], K[i])<sum){
return 0;
}
}
}
return 1;
}
