#include "bits/stdc++.h"
#include "teams.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'
struct Node {
int pref, suf, mn, sum;
};
class SegmentTree {
private:
vector<Node> tree; vi raw; int n;
int INF = 1e7;
Node bound = {0, 0, INF, 0};
Node merge(Node a, Node b) {
if (a.mn == -INF) return b;
if (b.mn == -INF) return a;
Node ans;
ans.sum = a.sum + b.sum;
ans.mn = min({a.mn, b.mn, b.pref + a.suf});
ans.suf = min(b.suf, b.sum + a.suf);
ans.pref = min(a.pref, a.sum + b.pref);
return ans;
}
void buildTree(int l, int r, int p) {
if (l == r) {
tree[p] = {raw[l], raw[l], raw[l], raw[l]};
return;
}
int mid = (l + r) / 2;
int c1 = 2*p+1, c2 = 2*p+2;
buildTree(l, mid, c1); buildTree(mid+1, r, c2);
tree[p] = merge(tree[c1], tree[c2]);
}
void update(int i, int val, int l, int r, int p) {
if (l > i or r < i) return;
if (l == r) {
val = val+tree[p].sum;
tree[p] = {val, val, val, val};
return;
}
int mid = (l + r) / 2;
int c1 = 2*p+1, c2 = 2*p+2;
update(i, val, l, mid, c1); update(i, val, mid+1, r, c2);
tree[p] = merge(tree[c1], tree[c2]);
}
Node mn(int i, int j, int l, int r, int p) {
if (l > j or r < i) return bound;
if (l >= i and r <= j) return tree[p];
int mid = (l + r) / 2;
int c1 = 2*p+1, c2 = 2*p+2;
return merge(mn(i, j, l, mid, c1), mn(i, j, mid+1, r, c2));
}
public:
void build(vi input) {
raw = input;
n = raw.size();
tree.resize(4*n);
buildTree(0, n-1, 0);
}
int mn(int i, int j) {
return mn(i, j, 0, n-1, 0).mn;
}
void update(int i, int val) {
update(i, val, 0, n-1, 0);
}
};
SegmentTree tree;
int n;
void init(int N, int A[], int B[]) {
n = N;
vi curr(N);
for_(i, 0, N) {
curr[A[i]-1]++;
if (B[i] < N) curr[B[i]]--;
}
for_(i, 1, N) curr[i] += curr[i-1];
tree.build(curr);
}
int can(int M, int K[]) {
for_(i, 0, M) {
tree.update(K[i]-1, -K[i]);
}
int ans = tree.mn(0, n-1) >= 0;
for_(i, 0, M) {
tree.update(K[i]-1, K[i]);
}
return ans;
}
// int main() {
// #ifdef mlocal
// freopen("teams.in", "r", stdin);
// #endif
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// int t; cin >> t;
// cout << "got " << t << endl;
// while (t--) {
// }
// }
