#include "teams.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 11;
int n;
int a[N], b[N];
int ed[N];
vector<pair<int, int>> stu;
namespace PerSeg{
int id = 0;
struct node{
node(int _s = 0): s(_s), ll(0), rr(0) {};
node(node* c, int ll, int rr) {
if(c[ll].s == -1 || c[rr].s == -1)
*this = c[ll].s == -1 ? c[rr] : c[ll];
else {
this->s = c[ll].s + c[rr].s;
this->ll = ll, this->rr = rr;
}
}
public:
int s, ll, rr;
};
int root[N];
node c[N * 30];
int build(int l, int r){
if(l == r){
c[id] = node();
return id++;
}else{
int tl = build(l, (l + r) / 2);
int tr = build((l + r) / 2 + 1, r);
c[id] = node(c, tl, tr);
return id++;
}
}
int add(int p, int v, int t, int l, int r){
if(l == r){
c[id] = node(c[t].s + v);
return id++;
}else{
int m = (l + r) / 2;
if(p <= m){
int tl = add(p, v, c[t].ll, l, m);
c[id] = node(c, tl, c[t].rr);
return id++;
}else{
int tr = add(p, v, c[t].rr, m + 1, r);
c[id] = node(c, c[t].ll, tr);
return id++;
}
}
}
int qry(int t, int ql, int qr, int l, int r){
if(r < ql || qr < l) return 0;
if(ql <= l && r <= qr) return c[t].s;
int m = (l + r) / 2;
return qry(c[t].ll, ql, qr, l, m)
+ qry(c[t].rr, ql, qr, m + 1, r);
}
void init(int n){
root[0] = build(1, n);
for(int i = 0; i < n; i++){
root[i + 1] = add(stu[i].se, 1, root[i], 1, n);
}
}
int qry(int l, int r, int y1, int y2){
r = min(r, n);
if(l > n || l > r) return 0;
return qry(root[r], y1, y2, 1, n)
- qry(root[l], y1, y2, 1, n);
}
int qry_bs_(int l, int r, int pref, int tl, int tr){
if(tl == tr){
if(c[r].s - c[l].s > pref) return tl - 1;
else return tl;
}
int tm = (tl + tr) / 2;
int t = c[c[r].ll].s - c[c[l].ll].s;
if(pref >= t){
return qry_bs_(c[l].rr, c[r].rr, pref - t, tm + 1, tr);
}else{
return qry_bs_(c[l].ll, c[r].ll, pref, tl, tm);
}
}
int qry_bs(int l, int r, int pref){
return qry_bs_(root[l], root[r], pref, 1, n);
}
};
namespace RMQ{
int st[20][N];
void init(int n, vector<int> a){
for(int i = 0; i < n; i++){
st[0][i] = a[i];
}
for(int j = 1; j < 20; j++){
for(int i = 0; i <= n - (1 << j); i++){
st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
}
}
}
int qry(int l, int r){
if(l > r) return INT32_MAX;
int d = __lg(r - l + 1);
return min(st[d][l], st[d][r - (1 << d) + 1]);
}
};
struct segment{
int l, r, d = 0, c = 0; // [l, r)
friend ostream& operator<< (ostream& out, const segment& a) {
return out << "segment [" << a.l << ", " << a.r << "): " << "min = " << a.d << ", " << "minc = " << a.c << "\n";
}
};
bool query(int k, vector<int>& s){
int idx = 0;
priority_queue<int, vector<int>, greater<int>> pq;
vector<segment> vs;
int cl = 0;
vs.push_back({0, 0, N - 1, 0});
int ccnt = 1;
for(auto i : s){
int cnt = 0;
vs.push_back({cl, ed[i] + 1, RMQ::qry(cl, ed[i])}); cl = ed[i] + 1;
while(vs.size() >= 2 && vs[vs.size() - 2].d < i){
vs[vs.size() - 2].r = vs[vs.size() - 1].r;
vs[vs.size() - 2].d = i;
vs[vs.size() - 2].c = 0;
vs.pop_back();
}
if(!vs.empty() && vs.back().d < i){
vs.back().d = i;
vs.back().c = 0;
}
while(vs.size() >= 2 && cnt < i){
int val = PerSeg::qry(vs.back().l, vs.back().r, vs.back().d, vs[vs.size() - 2].d - 1) - vs.back().c;
if(cnt + val <= i){
cnt += val;
vs[vs.size() - 2].r = vs[vs.size() - 1].r;
vs.pop_back();
}else{
break;
}
}
int rem = i - cnt;
int pref = rem + vs.back().c + PerSeg::qry(vs.back().l, vs.back().r, 1, vs.back().d - 1);
int h = PerSeg::qry_bs(vs.back().l, vs.back().r, pref);
int v = PerSeg::qry(vs.back().l, vs.back().r, vs.back().d, h);
vs.back().d = h + 1;
vs.back().c = rem + vs.back().c - v;
int q = PerSeg::qry(vs.back().l, vs.back().r, h + 1, h + 1);
if(q < rem - v)
return 0;
}
return 1;
}
void init(int N, int A[], int B[]) {
n = N;
for(int i = 0; i < n; i++){
stu.push_back({A[i], B[i]});
}
sort(stu.begin(), stu.end());
vector<int> stux;
for(auto i : stu){
stux.push_back(i.se);
}
RMQ::init(n, stux);
fill(ed + 1, ed + n + 1, -1);
for(int i = 0; i < n; i++){
ed[stu[i].fi] = max(ed[stu[i].fi], i);
}
for(int i = 1; i <= n; i++){
ed[i] = max(ed[i], ed[i - 1]);
}
PerSeg::init(n);
}
int can(int M, int K[]) {
vector<int> s;
for(int j = 0; j < M; j++){
s.push_back(K[j]);
}
sort(s.begin(), s.end());
return query(M, s);
}
