#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)5e5 + 100;
const int T = (int)1e7 + 100;
struct node{
int val;
int lef;
int rig;
};
int cur;
node V[T];
int n;
vector<pii> segm;
vector<pii> segt;
int upd(int node, int cl, int cr, int id, int vv){
int cid = cur;
V[cid].lef = -1;
V[cid].rig = -1;
if(node == -1)
V[cid].val = 0;
else{
V[cid].val = V[node].val;
V[cid].lef = V[node].lef;
V[cid].rig = V[node].rig;
}
V[cid].val += vv;
cur ++ ;
if(cl == cr) return cid;
int mid = (cl + cr) / 2;
if(id <= mid){
int go = V[cid].lef;
V[cid].lef = upd(go, cl, mid, id, vv);
}
else{
int go = V[cid].rig;
V[cid].rig = upd(go, mid + 1, cr, id, vv);
}
return cid;
}
int get(int node, int cl, int cr, int tl, int tr){
if(cr < tl || cl > tr) return 0;
if(node == -1) return 0;
if(cl >= tl && cr <= tr){
return V[node].val;
}
int mid = (cl + cr) / 2;
return get(V[node].lef, cl, mid, tl, tr) + get(V[node].rig, mid + 1, cr, tl, tr);
}
int root[N];
void init(int _N, int A[], int B[]) {
n = _N;
for(int i = 0 ; i < n; i ++ ){
segm.push_back(mp(A[i], B[i]));
segt.push_back(mp(B[i], A[i]));
}
sort(segm.begin(), segm.end());
sort(segt.begin(), segt.end());
int iq = 0;
root[0] = -1;
int dash;
for(int i = 1; i <= n; i ++ ){
root[i] = root[i - 1];
while(iq < segt.size() && segt[iq].fi <= i){
dash = upd(root[i], 1, n, segt[iq].se, +1);
root[i] = dash;
iq ++ ;
}
}
}
const int C = 400;
ll dp[C];
ll low[C];
int compute(int lf, int rf){
return get(root[rf], 1, n, lf, rf);
}
int can(int M, int K[]) {
vector<int> lis;
int m = M;
for(int j = 0; j < m ; j ++ ){
lis.push_back(K[j]);
}
sort(lis.begin(), lis.end());
bool sol0 = true, sol1 = true;
if(m >= C){
ll cum = 0;
for(auto x : lis) cum += x;
if(cum > n) {
sol0=false;
return false;
}
priority_queue<int, vector<int>, greater<int>> cv;
int iq = 0;
for(auto x : lis){
while(iq < segm.size() && segm[iq].fi <= x){
cv.push(segm[iq].se);
iq ++ ;
}
while(!cv.empty() && cv.top() < x)
cv.pop();
if(cv.size() < x){
sol0=false;
break;
}
for(int j = 0 ; j < x; j ++ ){
cv.pop();
}
}
return sol0;
}
else { // by hall
ll comp;
for(int j = 0 ; j < m ; j ++ ){
dp[j] = n - lis[j] - compute(1, lis[j] - 1);
for(int i = 0; i < j ; i ++ ){
dp[j] = min(dp[j], dp[i] - lis[j] - compute(lis[i] + 1, lis[j] - 1));
}
comp = dp[j] - compute(lis[j] + 1, n);
if(comp < 0){
sol1=false;
break;
}
}
return sol1;
}
return sol0;
}
