#include "teams.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;
const int N = 500010;
int n;
namespace seg {
vector<int> nds;
vector<int> ls;
int nxt = 1;
struct node {
int cnt, l, r;
} nd[(1<<27)/sizeof(node)];
int get(int t, int l, int r, int b, int e) {
if (l <= b && e <= r)
return nd[t].cnt;
int ans = 0;
if (l < (b+e)/2 && nd[t].l)
ans += get(nd[t].l, l, r, b, (b+e)/2);
if ((b+e)/2 < r && nd[t].r)
ans += get(nd[t].r, l, r, (b+e)/2, e);
return ans;
}
int add(int t, int p, int b, int e) {
int ans = nxt++;
nd[ans].cnt = nd[t].cnt+1;
nd[ans].l = nd[t].l;
nd[ans].r = nd[t].r;
if (e-b == 1)
return ans;
if (p < (b+e)/2)
nd[ans].l = add(nd[t].l, p, b, (b+e)/2);
else
nd[ans].r = add(nd[t].r, p, (b+e)/2, e);
return ans;
}
void mk_seg(const vector<pii> &vec) {
nds = {0};
int p = 0;
Loop (i,1,N+1) {
int t = nds.back();
while (p < vec.size() && vec[p].first < i)
t = add(t, vec[p++].second, 0, N);
nds.push_back(t);
}
}
int get(int l1, int r1, int l2, int r2) {
return get(nds[r1], l2, r2, 0, N)
- get(nds[l1], l2, r2, 0, N);
}
}
int cnt[N];
vector<pii> vec;
void init(int n, int a[], int b[]) {
Loop (i,0,n) {
cnt[a[i]]++;
cnt[b[i]+1]--;
vec.push_back({a[i], b[i]+1});
}
Loop (i,1,N)
cnt[i] += cnt[i-1];
::n = n;
sort(vec.begin(), vec.end());
seg::mk_seg(vec);
}
int can2(int m, int k[])
{
priority_queue<int,vector<int>,greater<int>> pq;
int p = 0;
Loop (i,0,m) {
while (p < vec.size() && vec[p].first <= k[i])
pq.push(vec[p++].second);
while (pq.size() && k[i] >= pq.top())
pq.pop();
if (pq.size() < k[i])
return 0;
if (i == m-1)
return 1;
Loop (_,0,k[i])
pq.pop();
}
return -1;
}
const int S = 700;
int can(int m, int k[]) {
ll sum = 0;
Loop (i,0,m)
sum += k[i];
if (sum > n)
return 0;
sort(k, k+m);
if (m > S)
return can2(m, k);
vector<int> dp(m);
LoopR (i,0,m) {
dp[i] = cnt[k[i]] - k[i];
Loop (j,i+1,m) {
int x = seg::get(0, k[i]+1, k[i]+1, k[j]+1);
x += dp[j] - k[i];
dp[i] = min(dp[i], x);
}
if (dp[i] < 0)
return 0;
}
return 1;
}
