#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<int, int> ii;
///segment tree begin
const int N = 1 << 19;
vector<int> tree[2*N];
inline void update(int a, int b){
for(b += N;b > 0;b >>= 1) tree[b].push_back(a);
}
inline void getready(){
for(int i = 0;i < 2*N;i++) sort(all(tree[i]));
}
inline int get(int u, int a, int A){
return upper_bound(all(tree[u]), A) - lower_bound(all(tree[u]), a);
}
inline int querypos(int a, int A, int need){
int u = 1;
for(int i = 1;i <= 19;i++){
int lc = u<<1; int rc = lc+1;
int G = get(rc,a,A);
if(need > G){
need -= G;
u = lc;
}
else u = rc;
}
return u-N;
}
inline int query(int a, int A, int l, int r){
int res = 0;
for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
if(l&1) res += get(l++,a,A);
if(r&1) res += get(--r,a,A);
}
return res;
}
///segment tree end
int cross[500005];
void init(int n, int A[], int B[]) {
for(int i = 0;i < n;i++) update(A[i], B[i]);
getready();
for(int i = 0;i < n;i++) cross[A[i]]++, cross[B[i]+1]--;
for(int i = 1;i <= 500000;i++) cross[i] += cross[i-1];
}
map<int,int> best;
priority_queue<ii, vector<ii>, greater<ii> > pq;
void create(int i){
auto b = best.find(i);
assert(b != best.begin() and b != best.end());
auto a = prev(b);
int diff = b->second - a->second;
int C = querypos(a->first+1, b->first, diff) + 1;
pq.push(ii(C,b->first));
}
void insert(int i, int dp){
if(best.empty()){
best[i] = dp;
return;
}
best[i] = dp;
create(i);
}
void process(int limit){
while(!pq.empty()){
ii T = pq.top();
if(T.first > limit) break;
pq.pop();
int i = T.second;
auto it = best.find(i);
if(it == best.end()) continue;
auto nxtit = next(it);
int nxt = -1;
if(nxtit != best.end()) nxt = nxtit->first;
best.erase(it);
if(nxt != -1) create(nxt);
}
}
int can(int M, int K[]) {
best.clear(); while(!pq.empty()) pq.pop();
sort(K,K+M);
long long total = 0;
for(int i = 0;i < M;i++) total += K[i];
if(total > 500000) return 0; ///idk why preemptive pruning
int acc = 0;
for(int i = 0;i < M;i++){
acc += K[i];
if(i != M-1 and K[i] == K[i+1]) continue; ///accumulate the queries
process(K[i]);
int dp = cross[K[i]]; ///dp = children - projects, if dp goes negative then return 0
if(not best.empty()){
auto it = best.end(); it--;
dp = min(dp, it->second + query(it->first+1, K[i], K[i], N-1));
}
dp -= acc;
if(dp < 0) return 0;
insert(K[i], dp);
acc = 0;
}
return 1;
}
