#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<":"<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif
namespace {
const int maxn = 5e5+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
}
int N;
vector<pii> seg;
int get(int L, int R) {
// temporary function
// returns the number of segments with index >= L && right value >= R
// to be replaced by segtree later
int re = 0;
for(int i = L; i<N; ++i) {
if(seg[i].s >= R) re++;
}
return re;
}
void init(signed NN, signed A[], signed B[]) {
N = NN;
seg.clear();
REP(i,N) {
seg.pb({A[i], B[i]});
}
sort(ALL(seg));
REP(i, N)bug(i,seg[i].f,seg[i].s);
}
struct item{
int L, R;
};
signed can(signed M, signed K[]) {
bug(M);
map<int, int> take;
REP(i,M) {
take[K[i]]+=K[i];
if (take[K[i]] > N) return 0;
}
vector<pii> tmp;
for(pii p :take) {
tmp.pb(p);
}
sort(ALL(tmp), greater<pii>());
vector<item > stk; // {L, R}
stk.pb({-1, N+1});
int goback = N;
for (auto PPP :tmp) {
int R = PPP.f;
int need = PPP.s;
while(goback-1 >= 0 && seg[goback-1].f > R) --goback;
int lastl = goback;
while (!stk.empty()) {
int sL = stk.back().L, sR = stk.back().R;
if (sL >= lastl) {
stk.pop_back(); continue;
}
// indicates that, of all segments of index in [sL, lastl),
// anything with right value >= sR was taken
int prv = lastl; lastl = sL;
int haverem = (get(sL,R) - get(prv,R)) - (get(sL,sR) - get(prv, sR));
bug(haverem);
if (haverem < need) {
need -= haverem;
stk.pop_back();
continue;
}else if (haverem == need) {
bug(haverem, need);
need -= haverem;
stk.back().R = R;
break;
}else{
bug(need);
int bl = sL + 1, br = prv - 1;
while (bl != br) {
int mid = (bl +br) / 2;
int yum = get(mid, R) - get(prv, R) - (get(mid, sR) - get(prv, sR));
bug(bl, br, mid, yum);
bug(prv, sR, R);
if(yum > need) {
bl = mid+1;
}else{
br = mid;
}
}
bug("add", bl, R);
stk.push_back({bl, R});
break;
}
}
if(stk.empty()) return 0;
}
bug("yay");
return 1;
}
/*
8
1 4
2 3
2 3
2 3
2 3
2 4
2 4
2 4
1
3 2 3 4
*/
