#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXM = 5e5;
struct node{
node *l,*r;
ll lazy;
};
void build(node *cur,ll l,ll r){
cur->lazy=0;
if (l!=r){
ll mid = (l + r) >> 1;
cur->l=new node;
cur->r=new node;
build(cur->l,l,mid);
build(cur->r,mid+1,r);
}
}
node* update(node* cur,ll l,ll r,ll i){
if (l > i || r < i)return cur;
if (l == r){
node* res = new node;
res->lazy=cur->lazy+1;
res->l=cur->l;
res->r=cur->r;
return res;
}
ll mid = (l + r) >> 1;
node *res = new node;
res->l = update(cur->l,l,mid,i);
res->r = update(cur->r,mid+1,r,i);
res->lazy=res->l->lazy+res->r->lazy;
return res;
}
node* update(node* cur,ll i){
// cout<<"UPDATE "<<l<<' '<<r<<' '<<val<<endl;
return update(cur,0,MAXM,i);
}
ll get(node* cur,ll l,ll r,ll l1,ll r1){
if (l > r1 || l1 > r || l1 > r1)return 0;
if (l1 <= l && r <= r1)return cur->lazy;
ll mid = (l + r) >> 1;
return get(cur->l,l,mid,l1,r1)+get(cur->r,mid+1,r,l1,r1);
}
ll get(node* cur,ll l,ll r){
return get(cur,0,MAXM,l,r);
}
node *tree[MAXM+100];
ll query(ll l,ll r){
return get(tree[r],l+1,r);
}
vector <pll> a;
ll n;
void init(int N, int A[], int B[]) {
n=N;
for (ll i = 0;i < n;i ++){
a.push_back({B[i],A[i]});
}
sort(a.begin(),a.end(),greater <> ());
tree[MAXM+1]=new node;
build(tree[MAXM+1],0,MAXM);
for (ll i = MAXM,ptr = 0;i >= 1;i --){
tree[i] = tree[i+1];
while (ptr < sz(a) && a[ptr].fi >= i){
tree[i] = update(tree[i],a[ptr].se);
ptr++;
}
}
}
ll b[MAXM+100];
ll m;
int can(int M, int K[]) {
// if (n > 100000)return 0;
m=M;
ll sum = 0;
for (ll i = 0;i < m;i ++){b[i] = K[i];sum += b[i];}
if (sum > n)return 0;
sort(b,b+m);
vector <pll> c;
for (ll i =0 ;i < m;i ++){
if (sz(c)!=0&&c.back().fi==b[i]){
c.back().se++;
}
else{
c.push_back(MP(b[i],1));
}
}
vector <ll> dp(sz(c));
set <ll> s;
set <pll> del;
for (ll i = 0;i < sz(c);i ++){
auto add_del=[&](set <ll> :: iterator tmp)->void{
if (tmp==s.begin())return;
ll x = *(prev(tmp));
ll l = i;
ll r = sz(c)-1;
while (l <= r){
ll mid = (l + r) >> 1;
if (dp[x] - query(c[x].fi,c[mid].fi) > dp[*tmp] - query(c[*tmp].fi,c[mid].fi)){
r = mid - 1;
}
else{
l = mid + 1;
}
}
del.insert(MP(l,*tmp));
};
if (i){
auto tmp = s.insert(i-1);
add_del(tmp.fi);
}
while (sz(del) && (*(del.begin())).fi == i){
auto x = s.find((*(del.begin())).se);
del.erase(del.begin());
if (x==s.end())continue;
auto tmp=s.erase(x);
if (tmp!=s.end()){
add_del(tmp);
}
}
dp[i] = c[i].fi*c[i].se-query(0,c[i].fi);
if (sz(s)){
ll j = *(s.rbegin());
dp[i] = max(dp[i],dp[j] + c[i].fi*c[i].se-query(c[j].fi,c[i].fi));
}
if (dp[i] > 0)return 0;
}
return 1;
}
