#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << x << endl;
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int MAXN = 1e6 + 10;
const int INF = 1e9 + 10;
struct node {
node *lc, *rc;
int val;
node() {}
node(int val_): lc(nullptr), rc(nullptr), val(val_) {}
node(node* lc_, node* rc_): lc(lc_), rc(rc_) {
val = lc_ -> val + rc_ -> val;
}
};
namespace segment {
node* sg[MAXN];
node* build(int l, int r) {
if (l == r) return new node(0);
int mid = (l + r) >> 1;
return new node(build(l, mid), build(mid + 1, r));
}
node* update(int ind, int l, int r, node* v) {
if (l == r) return new node((v -> val) + 1);
int mid = (l + r) >> 1;
if (ind <= mid) return new node(update(ind, l, mid, v -> lc), v -> rc);
else return new node(v -> lc, update(ind, mid + 1, r, v -> rc));
}
int query(int ql, int qr, int l, int r, node* v) {
if (ql > r || qr < l) return 0;
if (ql <= l && qr >= r) return v -> val;
int mid = (l + r) >> 1;
return query(ql, qr, l, mid, v -> lc) +
query(ql, qr, mid + 1, r, v -> rc);
}
}
namespace segment2 {
int sg[MAXN], lz[MAXN];
inline void push(int v) {
sg[v] += lz[v];
if ((v << 1 | 1) < MAXN)
lz[v << 1] += lz[v], lz[v << 1 | 1] += lz[v];
lz[v] = 0;
}
void build(int l, int r, int v) {
lz[v] = 0;
if (l == r) sg[v] = -INF;
else {
int mid = (l + r) >> 1;
build(l, mid, v << 1);
build(mid + 1, r, v << 1 | 1);
sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
}
}
void update(int ql, int qr, int val, int l, int r, int v) {
push(v);
if (ql > r || qr < l) return;
if (ql <= l && qr >= r) {
lz[v] += val;
push(v);
return;
}
int mid = (l + r) >> 1;
update(ql, qr, val, l, mid, v << 1);
update(ql, qr, val, mid + 1, r, v << 1 | 1);
sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
}
void point_set(int ind, int val, int l, int r, int v) {
push(v);
if (l == r) sg[v] = val;
else {
int mid = (l + r) >> 1;
if (ind <= mid) point_set(ind, val, l, mid, v << 1), push(v << 1 | 1);
else point_set(ind, val, mid + 1, r, v << 1 | 1), push(v << 1);
sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
}
}
}
int n;
vector<int> R[MAXN];
void init(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n; i++)
R[B[i]].push_back(A[i]);
segment::sg[0] = segment::build(1, n);
for (int i = 1; i <= n; i++) {
node* v = segment::sg[i - 1];
for (int l : R[i])
v = segment::update(l, 1, n, v);
segment::sg[i] = v;
}
}
inline int get(int l, int r) {
if (r < l) return 0;
return segment::query(l, n, 1, n, segment::sg[r]);
}
int can(int M, int K[]) {
int m = M;
vector<int> vec;
vec.push_back(0);
int s = 0;
for (int i = 0; i < m; i++) {
vec.push_back(K[i]);
s += K[i];
if (s > n) return 0;
}
sort(all(vec));
segment2::build(1, m, 1);
int ans = -INF;
for (int i = 1; i <= m; i++) {
if (i > 1) segment2::update(1, i - 1, vec[i] + get(vec[i - 1] + 1, vec[i] - 1), 1, m, 1);
segment2::point_set(i, get(1, vec[i] - 1) + vec[i], 1, m, 1);
ans = max(ans, segment2::sg[1] + get(vec[i] + 1, n));
}
if (n < ans) return 0;
return 1;
}
