#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 5e5 + 5;
int n,m,tree[30 * N], le_[30 * N], ri_[30 * N], cur, k[N], dp[N],a[N],b[N],root[N];
vector <int> v[N];
set <int> s1;
set <pii> s;
int merge(int a, int b) {
return a + b;
}
void build(int node, int le, int ri) {
if (le == ri) {
return ;
}
le_[node] = ++cur;
ri_[node] = ++cur;
int mid = (le + ri) / 2;
build(le_[node], le, mid);
build(ri_[node], mid + 1, ri);
tree[node] = merge(tree[le_[node]], tree[ri_[node]]);
}
void update(int node, int le, int ri, int idx, int val) {
if (le > idx || ri < idx) return ;
if (le == ri) {
tree[cur] = tree[node] + val;
return ;
}
int mid = (le + ri) / 2;
int vert = cur;
le_[cur] = le_[node];
ri_[cur] = ri_[node];
if (idx <= mid) {
le_[vert] = ++cur;
}
else {
ri_[vert] = ++cur;
}
update(le_[node], le, mid, idx, val);
update(ri_[node], mid + 1, ri, idx, val);
tree[vert] = merge(tree[le_[vert]], tree[ri_[vert]]);
}
int getans(int node, int le, int ri, int start, int end) {
if (le > end || ri < start) return 0;
if (le >= start && ri <= end) return tree[node];
int mid = (le + ri) / 2;
return merge(getans(le_[node], le, mid, start, end), getans(ri_[node], mid + 1, ri, start, end));
}
void init(int N, int A[], int B[]) {
n = N;
for (int i = 1; i <= n; i++) {
a[i] = A[i - 1]; b[i] = B[i - 1];
v[a[i]].pb(b[i]);
}
root[0] = 1; cur = 1;
build(1, 1, n);
for (int i = 1; i <= n; i++) {
root[i] = root[i - 1];
for (int x : v[i]) {
int pr_root = root[i];
root[i] = ++cur;
update(pr_root, 1, n, x, 1);
}
}
}
int get(int i, int j) {
int le = k[j] + 1, ri = n, ans = 0;
while (le <= ri) {
int mid = (le + ri) / 2;
if (dp[i] + (getans(root[k[j]], 1,n, mid, n) - getans(root[k[i]],1,n, mid, n)) < dp[j]) {
ans = mid; ri = mid - 1;
} else le = mid + 1;
}
return ans;
}
void del(int idx) {
if (!s1.count(idx)) return ;
s1.erase(idx);
auto it = s1.upper_bound(idx);
int nxt = (it == s1.end() ? -1 : *it);
int pre = (it == s1.begin() ? -1 : *(--it));
if (pre != -1) {
if (get(pre, idx)) s.erase({get(pre, idx), idx});
}
if (nxt != -1) {
if (get(idx, nxt)) s.erase({get(idx, nxt), nxt});
}
if (pre != -1 && nxt != -1) {
if (get(pre, nxt)) s.insert({get(pre, nxt), nxt});
}
}
void add(int idx) {
if (s1.count(idx)) return ;
if (!s1.size()) { s1.insert(idx); return ; }
auto it = s1.upper_bound(idx);
int nxt = (it == s1.end() ? -1 : *it);
int pre = (it == s1.begin() ? -1 : *(--it));
if (pre != -1 && nxt != -1) {
if (get(pre, nxt)) s.erase({get(pre, nxt), nxt});
}
if (pre != -1) if(get(pre, idx)) s.insert({get(pre, idx), idx});
if (nxt != -1) if (get(idx, nxt)) s.insert({get(idx, nxt), nxt});
s1.insert(idx);
}
int can(int M, int K[]) {
s.clear(); s1.clear();
m = M;
for (int i = 1; i <= m; i++) {
k[i] = K[i - 1]; dp[i] = 0;
}
sort(k + 1, k + m + 1);
add(0);
for (int i = 1; i <= m; i++) {
while (s.size() && (*s.begin()).f <= k[i]) {
del((*s.begin()).s);
}
int id = (*--s1.end());
dp[i] = dp[id] + getans(root[k[i]], 1, n, k[i], n) - getans(root[k[id]], 1, n, k[i], n) - k[i];
if (dp[i] < 0) {
return 0;
}
add(i);
}
return 1;
}
