#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int MAXN = (int) 5e5 + 5;
vector<ll> t[4*MAXN];
void add(int v, int tl, int tr, int val, int pos){
if(tl == tr){
t[v].push_back(val);
}else{
int tm = (tl + tr) / 2;
if(pos <= tm){
add(2*v, tl, tm, val, pos);
}else{
add(2*v+1, tm + 1, tr, val, pos);
}
t[v].push_back(val);
}
}
ll que(int v, int tl, int tr, int l, int r, int val){
if(l > r) return 0;
if(tl == l && tr == r){
return t[v].end() - lower_bound(t[v].begin(), t[v].end(), val);
}else{
int tm = (tl + tr) / 2;
return que(2*v, tl, tm, l, min(tm, r), val) + que(2*v+1, tm + 1, tr, max(tm + 1, l), r, val);
}
}
void init(int N, int A[], int B[]) {
n = N;
for(int i = 0; i < N; i++){
add(1, 1, N, B[i], A[i]);
}
for(int i = 1; i < 4*MAXN; i++) sort(t[i].begin(), t[i].end());
}
ll dp[MAXN];
int can(int M, int K[]) {
int N = n;
sort(K, K + M);
vector<ll> lst;
dp[0] = que(1, 1, N , 1, K[0], K[0]) - K[0];
if(dp[0] < 0) return 0;
lst.push_back(0);
for(int i = 1; i < M; i++){
dp[i] = que(1, 1, N, 1, K[i], K[i]) - K[i];
while(lst.size() > 1){
int cur = lst.back();
lst.pop_back();
ll deg1 = dp[cur] + que(1, 1, N, K[cur] + 1, K[i], K[i]);
ll deg2 = dp[lst.back()] + que(1, 1, N , K[lst.back()] + 1, K[i], K[i]);
if(deg2 > deg1){
lst.push_back(cur);
break;
}
}
dp[i] = min(dp[i], dp[lst.back()] + que(1, 1, N, K[lst.back()] + 1, K[i], K[i]) - K[i]);
lst.push_back(i);
if(dp[i] < 0) return 0;
}
return 1;
}
