#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
// #undef BALBIT
// #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;
const int BA= 40;
}
int N;
vector<pii> seg;
namespace MAO{
int lc[maxn*BA], rc[maxn*BA], val[maxn*BA];
int history[maxn];
int IT = 1;
int MO(int p, int o, int l, int r) {
if (l > p || r < p) return o;
int NO = ++IT;
val[NO] = val[o] + 1;
if (l == r) {
return NO;
}
int mid = (l+r)/2;
lc[NO] = MO(p,lc[o],l,mid);
rc[NO] = MO(p,rc[o],mid+1,r);
return NO;
}
int build(int l, int r) {
int NO = ++IT;
if (l == r) {
return NO;
}
int mid = (l+r)/2;
lc[NO] = build(l,mid); rc[NO] = build(mid+1,r);
return NO;
}
int yeah[maxn*BA];
vector<int> yoo;
int QU(int L, int R, int o, int l, int r) {
// bug(p,l,r,o,val[o]);
if (~yeah[o]) return yeah[o];
if (l > R || r < L) return 0;
if (l >= L && r <= R) {
return val[o];
}
int mid = (l+r) >> 1;
yoo.pb(o);
return yeah[o] = QU(L,R,lc[o],l,mid) + QU(L,R,rc[o],mid+1,r);
}
int QUsimple(int L, int R, int o, int l, int r) {
// bug(p,l,r,o,val[o]);
if (l > R || r < L) return 0;
if (l >= L && r <= R) {
return val[o];
}
int mid = (l+r) >> 1;
return QUsimple(L,R,lc[o],l,mid) + QUsimple(L,R,rc[o],mid+1,r);
}
}
inline int get(int L, int Ra, int Rb, bool rep=0) {
// 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;
if (L >= N || Ra > N || Ra-1 > Rb) return 0;
// bug(L,R);
MX(L, 0);
int ret = rep?MAO::QU(Ra-1, Rb-1,MAO::history[L],0,N-1) : MAO::QUsimple(Ra-1, Rb-1,MAO::history[L],0,N-1);
return ret;
}
void init(signed NN, signed A[], signed B[]) {
memset(MAO::lc, -1, sizeof MAO::lc);
memset(MAO::rc, -1, sizeof MAO::rc);
memset(MAO::yeah, -1, sizeof MAO::yeah);
memset(MAO::val, 0, sizeof MAO::val);
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);
MAO::history[N] = MAO::build(0, N-1);
bug(MAO::history[N]);
for(int i = N-1; i>=0; --i) {
MAO::history[i] = MAO::MO(seg[i].s-1,MAO::history[i+1],0,N-1);
}
// bug(MAO::QU(0,MAO::history[0],0,N-1));
// bug(MAO::QU(1,MAO::history[0],0,N-1));
// bug(MAO::QU(2,MAO::history[0],0,N-1));
// bug(MAO::QU(3,MAO::history[0],0,N-1));
}
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;
{
int bl = 0, br = goback;
while (bl != br) {
int mid = (bl + br) / 2;
if(seg[mid].f > R) {
br = mid;
}else{
bl = mid+1;
}
}
goback = bl;
}
// 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, sR-1)
-get(prv, R, sR-1);
// (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 - need;
for (int e : MAO::yoo) {
MAO::yeah[e] = -1;
}
MAO::yoo.clear();
int fix = -get(prv, R,sR-1);
// {
// int yar = fix +get(br, R, sR-1);
// if(yar == need) {
// bl = br;
// }
// }
while (bl != br) {
int mid = (bl +br) / 2;
int yum = fix + get(mid, R, sR-1,1) ;
bug(bl, br, mid, yum);
bug(prv, sR, R);
if (yum == need){
bl = br = mid; break;
}
if(yum > need) {
bl = mid+(yum-need);
}else{
br = mid-(need-yum);
}
}
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
*/
