#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 = 3e5 + 5;
int le_[N * 20], ri_[N * 20], root[N], tree[N * 20], n, cur, prev[N], k[N], a[N], b[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];
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;
return tree[u] + get(le_[u], id, l, mid) + 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);
set<int> s; set<pii> bet;
s.insert(0);
for(int i = 1; i <= M; i++) {
k[i] = K[i - 1];
}
for(int i = 1; i <= M; i++) {
while(bet.size() && (*bet.begin()).f <= k[i]) {
pii p = *bet.begin();
bet.erase(p);
int r = p.s, l = *--s.upper_bound(r - 1);
s.erase(l);
if(s.upper_bound(l - 1) != s.begin()) {
int p = *--s.upper_bound(l - 1);
bet.erase({prev[l], l});
prev[r] = get(p, r);
bet.insert({prev[r], r});
}
}
int x = *s.begin();
dp[i] = dp[x] + k[i] - get(root[k[x] + 1], k[i], 1, n);
// cout << k[i] <<" __ "<< dp[i] << " __ " <<dp[x] + k[i] - get(root[1], 1, 1, n) << endl;
s.insert(i);
prev[i] = get(*--s.end(), i);
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;
} */
