#include "teams.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int MAXN = 5e5 + 12, BS = 300;
struct node{
int val = 0;
node *l = nullptr, *r = nullptr;
node(int _val = 0, node* _l = nullptr, node* _r = nullptr){
val = _val, l = _l, r = _r;
}
};
int getVal(node* v){
return v ? v->val: 0;
}
node* upd(node* v, int tl, int tr, int pos, int val){
if(tl == tr) return new node(getVal(v) + val);
int tm = (tl + tr) / 2;
if(pos <= tm) v = new node(0, upd(v ? v->l: v, tl, tm, pos, val), v ? v->r: v);
else v = new node(0, v ? v->l: v, upd(v ? v->r: v, tm + 1, tr, pos, val));
v->val = getVal(v->l) + getVal(v->r);
return v;
}
int get(node* v, int tl, int tr, int l, int r){
if(tl > r || l > tr) return 0;
if(tl >= l && tr <= r) return getVal(v);
int tm = (tl + tr) / 2;
return (v->l ? get(v->l, tl, tm, l, r): 0) + (v->r ? get(v->r, tm + 1, tr, l, r): 0);
}
node* root[MAXN];
int n, dp[MAXN];
vector< int > rv[MAXN], mine[MAXN];
void init(int N, int A[], int B[]) {
n = N, root[0] = new node();
for(int i = 0;i < n;i++)
rv[n - B[i] + 1].push_back(A[i]), mine[A[i]].push_back(B[i]);
for(int i = 1;i <= n;i++){
root[i] = root[i - 1];
for(int v: rv[i]){
root[i] = upd(root[i], 1, n, v, 1);
}
}
}
int cf(int l, int r){
return get(root[n - r + 1], 1, n, l, r);
}
int can(int M, int K[]) {
sort(K, K + M);
vector< int > opt; int ptr = -1;
for(int i = 0;i < M;i++){
dp[i] = cf(1, K[i]) - K[i];
while(ptr >= 1 && dp[opt[ptr - 1]] + cf(K[opt[ptr - 1]] + 1, K[i]) < dp[opt[ptr]] + cf(K[opt[ptr]] + 1, K[i])) opt.pop_back(), ptr--;
if(ptr >= 0) dp[i] = min(dp[i], dp[opt[ptr]] + cf(K[opt[ptr]] + 1, K[i]) - K[i]);
ptr++, opt.push_back(i);
if(dp[i] < 0) return 0;
}
return 1;
}
