#include <bits/stdc++.h>
#include "teams.h"
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
constexpr int maxn = 5e5+10, SZ = 100;
std::priority_queue<int, std::vector<int>, std::greater<int>> q;
int a[maxn], b[maxn], n;
pii range[maxn];
int ind[maxn];
int opt[maxn];
struct Node
{
Node *l, *r;
int v;
Node()
{
l = r = NULL;
v = 0;
}
} *version[maxn];
struct PersistentSegmentTree
{
void build(Node *node, int l, int r)
{
if (l == r) return;
int mid = (l+r)>>1;
node->l = new Node(); node->r = new Node();
build(node->l, l, mid); build(node->r, mid+1, r);
}
void upd(Node *prev, Node *node, int l, int r, int pos, int v)
{
if (l == r)
{
node->v = prev->v + v;
return;
}
int mid = (l+r)>>1;
if (pos <= mid)
{
if (!node->l) node->l = new Node();
node->r = prev->r;
upd(prev->l, node->l, l, mid, pos, v);
}
else
{
if (!node->r) node->r = new Node();
node->l = prev->l;
upd(prev->r, node->r, mid+1, r, pos, v);
}
node->v = node->l->v + node->r->v;
}
int query(Node *prev, Node *node, int l, int r, int a, int b)
{
if (l > b || r < a) return 0;
if (l >= a && r <= b) return node->v - prev->v;
int mid = (l+r)>>1;
return query(prev->l, node->l, l, mid, a, b) + query(prev->r, node->r, mid+1, r, a, b);
}
int get(int l, int r, int k)
{
return query(version[ind[l]], version[ind[r]], 1, n, k, n);
}
} seg;
void init(int N, int A[], int B[]) {
n = N;
for(int i = 0; i < N; i++)
a[i] = A[i], b[i] = B[i];
for (int i = 1; i <= n; i++)
range[i] = {A[i-1], B[i-1]};
sort(range+1, range+n+1);
int ptr = 1, aux = 0;
version[0] = new Node();
seg.build(version[0], 1, n);
for (int i = 1; i <= n; i++)
{
while (ptr <= n && range[ptr].ff == i)
{
version[++aux] = new Node();
seg.upd(version[aux-1], version[aux], 1, n, range[ptr].ss, 1);
ptr++;
}
ind[i] = aux;
}
}
struct Event
{
int t, x, r;
bool operator<(Event e) { if(x == e.x) return t < e.t; return x < e.x; }
};
std::vector<Event> events;
int greedy(int M, int K[]) {
events.clear();
while(q.size()) q.pop();
for(int i = 0; i < n; i++)
events.push_back({0, a[i], b[i]});
for(int i = 0; i < M; i++)
events.push_back({1, K[i], K[i]});
std::sort(events.begin(), events.end());
for(auto e : events) {
while(q.size() && q.top() < e.x)
q.pop();
if(!e.t) q.push(e.r);
else {
while(e.r--) {
if(!q.size()) return 0;
q.pop();
}
}
}
return 1;
}
ll dp[maxn];
int fq[maxn];
void solve(vector<int> &V, int l, int r)
{
if (l > r) return;
for (int i = 0; i < V.size(); i++)
{
int k = V[i];
dp[i] = 1ll*seg.get(0, k, k) - 1ll*fq[k]*k;
for (int j = 0; j < i; j++)
dp[i] = min(dp[i], dp[j] + 1ll*seg.get(V[j], k, k) - 1ll*fq[k]*k);
}
}
int can(int M, int K[]) {
if(M > 50) return greedy(M, K);
int m = M;
vector<int> V;
for (int i = 0; i < m; i++)
{
V.push_back(K[i]);
fq[K[i]]++;
}
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
m = V.size();
solve(V, 0, m-1);
bool ok = 1;
for (int j = 0; j < m; j++)
{
if (dp[j] < 0) ok = 0;
dp[j] = fq[V[j]] = opt[j] = 0;
}
return ok;
}
