#include "teams.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define prev Prev
#define f first
#define s second
using namespace std;
const int N = 15e5 + 5;
int le_[N * 20], ri_[N * 20], root[N], tree[N * 20], n, cur, prev[N], k[N], a[N], b[N], nxt[N], p[N], rem[N];
long long dp[N];
void build(int u,int l,int r) {
if(l == r) return;
int mid = (l + r) / 2;
le_[u] = ++cur; ri_[u] = ++cur;
build(le_[u], l, mid); build(ri_[u], mid + 1, r);
}
void upd(int u,int st,int en,int l,int r) {
if(l > en || r < st) return;
le_[cur] = le_[u], ri_[cur] = ri_[u];
tree[cur] = tree[u];
assert(cur <= N * 35);
if(st <= l && r <= en) {
tree[cur]++;
return;
}
int mid = (l + r) / 2, x = cur;
if(st <= mid) {
le_[x] = ++cur;
}
upd(le_[u], st, en, l, mid);
if(en > mid) {
ri_[x] = ++cur;
}
upd(ri_[u], st, en, mid + 1, r);
}
int get(int u,int id, int l,int r) {
if(id > r || id < l) return 0;
if(l == r) return tree[u];
int mid = (l + r) >> 1;
if(id <= mid) return tree[u] + get(le_[u], id, l, mid);
return tree[u] + get(ri_[u], id, mid + 1, r);
}
void init(int N, int A[], int B[]) {
n = N;
vector<int> V[n + 2];
for(int i = 0; i < n; i++) V[A[i]].push_back(B[i]);
cur = root[n + 1] = 1;
build(1, 1, n);
for(int i = n; i >= 1; i--) {
root[i] = root[i + 1];
for(int j = 0; j < V[i].size(); j++) {
cur++;
int x = cur;
upd(root[i], i, V[i][j], 1, n);
root[i] = x;
}
}
}
int get(int i, int j) {
int l = k[j] + 1, r = n, ans = n + 1;
while(l <= r) {
int mid = (l + r) / 2;
if(dp[i] - get(root[k[i] + 1], mid, 1, n) >= dp[j] - get(root[k[j] + 1], mid, 1, n)) ans = mid, r = mid - 1;
else l = mid + 1;
}
return ans;
}
int can(int M, int K[]) {
sort(K, K + M);
vector<int> s; set<pii> bet;
s.push_back(0);
for(int i = 1; i <= M; i++) {
k[i] = K[i - 1]; rem[i] = 0; nxt[i] = p[i] = 0;
}
for(int i = 1; i <= M; i++) {
while(bet.size() && (*bet.begin()).f <= k[i]) {
pii po = *bet.begin();
bet.erase(po);
int r = po.s, l = p[r];
rem[r] = 1;
if(nxt[r]) {
nxt[l] = nxt[r];
p[nxt[l]] = l;
int x = nxt[l];
bet.erase({prev[x], x});
prev[x] = get(l, x);
bet.insert({prev[x], x});
}
}
while(s.size() && rem[s.back()]) s.pop_back();
int x = s.back();
dp[i] = dp[x] + k[i] - get(root[k[x] + 1], k[i], 1, n);
prev[i] = get(x, i);s.push_back(i); nxt[x] = i; p[i] = x;
bet.insert({prev[i], i});
if(dp[i] > 0) return 0;
}
return 1;
}
/*
int main() {
// _inputFile = fopen("teams.in", "rb");
// _outputFile = fopen("teams.out", "w");
int n, q;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
init(n, a, b);
cin >> q;
while(q--) {
int k;
cin >> k;
int v[k + 2];
for(int i = 0; i < k; i++) cin >> v[i];
cout << can(k, v) << endl;
}
return 0;
} */
