#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cerr << #x << ": " << x << endl;
#define all(x) (x).begin(), (x).end()
const int MAXN = 4e6 + 10;
const int INF = 1e9 + 10;
struct node {
node *lc, *rc;
ll val;
node() {}
node(ll 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);
}
}
int n, ps[MAXN];
vector<int> R[MAXN];
int dp[MAXN], F[MAXN];
vector<int> vec;
inline int get(int l, int r) {
if (r < l) return 0;
return segment::query(l, n, 1, n, segment::sg[r]);
}
inline int cov(int l, int r) {
ll s = ps[r] - ps[l - 1];
return s - get(l, r - 1);
}
namespace li_chao {
int best[MAXN], T[MAXN];
inline int calc(int ind, int x) {
// if (x <= vec[ind]) return INF;
return dp[ind] + cov(vec[ind] + 1, x);
}
void add(int f, int l = 1, int r = n + 1, int v = 1) {
T[v] = 1;
int m = (l + r) >> 1;
bool lf = calc(f, l) < calc(best[v], l);
bool md = calc(f, m) < calc(best[v], m);
if (md) swap(best[v], f);
if (r - l == 1) return;
else if (lf != md) add(f, l, m, v << 1);
else add(f, m, r, v << 1 | 1);
}
int query(int x, int l = 1, int r = n + 1, int v = 1) {
int m = (l + r) >> 1;
if (r - l == 1) return calc(best[v], x);
else if (x < m) return min(calc(best[v], x), query(x, l, m, v << 1));
else return min(calc(best[v], x), query(x, m, r, v << 1 | 1));
}
void clear(int l = 1, int r = n + 1, int v = 1) {
best[v] = 0;
if (r - l == 1 || !T[v]) {
T[v] = 0;
return;
}
T[v] = 0;
int m = (l + r) >> 1;
clear(l, m, v << 1);
clear(m, r, v << 1 | 1);
}
}
void init(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n; i++) {
R[B[i]].push_back(A[i]);
ps[A[i]]++;
}
for (int i = 1; i <= n; i++) ps[i] += ps[i - 1];
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 void clear(int M, int K[]) {
vec.clear();
for (int i = 0; i < M; i++) {
F[K[i]] = 0;
dp[i] = 0;
}
dp[M] = 0;
li_chao::clear();
}
int can(int M, int K[]) {
int m = M, s = 0;
for (int i = 0; i < m; i++) {
s += K[i];
if (s > n) {
clear(M, K);
return 0;
}
F[K[i]] += K[i];
vec.push_back(K[i]);
}
sort(all(vec));
vec.resize(unique(all(vec)) - vec.begin());
vec.insert(vec.begin(), 0);
dp[0] = 0;
m = vec.size();
for (int i = 1; i < m; i++) {
dp[i] = numeric_limits<int>::max();
dp[i] = li_chao::query(vec[i]) - F[vec[i]];
if (dp[i] < 0) {
clear(M, K);
return 0;
}
li_chao::add(i);
}
clear(M, K);
return 1;
}
