#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 3;
vector <int> merge(vector <int> &a, vector <int> &b)
{
vector <int> ans;
int pos_a = 0, pos_b = 0, sz_a = (int)a.size(), sz_b = (int)b.size();
while (pos_a < sz_a && pos_b < sz_b)
{
if (a[pos_a] < b[pos_b])
{
ans.push_back(a[pos_a]);
pos_a++;
}
else
{
ans.push_back(b[pos_b]);
pos_b++;
}
}
while (pos_a < sz_a)
{
ans.push_back(a[pos_a]);
pos_a++;
}
while (pos_b < sz_b)
{
ans.push_back(b[pos_b]);
pos_b++;
}
return ans;
}
int n;
vector <int> ve[maxn];
vector <int> tr[maxn * 4];
void build(int v, int l, int r)
{
if (l == r)
{
tr[v] = ve[l];
sort (tr[v].begin(), tr[v].end());
return;
}
int mid = (l + r) / 2;
build(v * 2, l, mid);
build(v * 2 + 1, mid + 1, r);
tr[v] = merge(tr[v * 2], tr[v * 2 + 1]);
}
vector <int> temp;
void get(int v, int l, int r, int ll, int rr)
{
if (l > rr || r < ll)
return;
if (l >= ll && r <= rr)
{
temp.push_back(v);
return;
}
int mid = (l + r) / 2;
get(v * 2, l, mid, ll, rr);
get(v * 2 + 1, mid + 1, r, ll, rr);
}
void init(int _n, int l[], int r[])
{
n = _n;
for (int i = 1; i <= n; i++)
ve[l[i-1]].push_back(r[i-1]);
build(1, 1, n);
}
int cnt[maxn];
bool can(int m, int k[])
{
long long sum = 0;
for (int i = 0; i < m; i++)
sum += k[i];
if (sum > n)
return false;
map <int, int> mp;
for (int i = 0; i < m; i++)
mp[k[i]]++;
for (int i = 0; i < (int)mp.size(); i++)
cnt[i] = 0;
int idx = 0;
for (auto it = mp.begin(); it != mp.end(); it++)
{
int prv = 1;
if (it != mp.begin())
prv = prev(it)->first + 1;
temp.clear();
get(1, 1, n, prv, it->first);
int curr_idx = idx;
for (auto it1 = it; it1 != mp.end(); it1++)
{
int nxt = n;
if (it1 != prev(mp.end()))
nxt = next(it1)->first - 1;
for (auto i: temp)
{
auto it2 = lower_bound(tr[i].begin(), tr[i].end(), it1->first);
auto it3 = upper_bound(tr[i].begin(), tr[i].end(), nxt);
cnt[curr_idx] += it3 - it2;
}
curr_idx++;
}
int to_sub = it->second * it->first;
for (int i = idx; i < (int)mp.size() && to_sub; i++)
{
int curr_to_sub = min(cnt[i], to_sub);
to_sub -= curr_to_sub;
cnt[i] -= curr_to_sub;
}
if (to_sub)
return false;
idx++;
}
return true;
}
