#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 = 2e5;
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 l1,ll r1){
if (l > r1 || l1 > r)return cur;
if (l1 <= l && r <= r1){
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->lazy=cur->lazy;
res->l = update(cur->l,l,mid,l1,r1);
res->r = update(cur->r,mid+1,r,l1,r1);
return res;
}
node* update(node* cur,ll l,ll r){
return update(cur,0,MAXM,l,r);
}
ll get(node* cur,ll l,ll r,ll i,ll val){
if (l==r){
return val + cur->lazy;
}
ll mid = (l + r) >> 1;
val += cur->lazy;
if (mid >= i)return get(cur->l,l,mid,i,val);
return get(cur->r,mid+1,r,i,val);
}
ll get(node* cur,ll i){
return get(cur,0,MAXM,i,0);
}
node *tree[MAXM+100];
pll a[500100];
ll query(ll l,ll r){
return get(tree[r],l);
}
void init(int n, int A[], int B[]) {
for (ll i = 0;i < n;i ++){
a[i] = MP(B[i],A[i]);
}
sort(a,a+n,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 < n && a[ptr].fi >= i){
tree[i] = update(tree[i],0,a[ptr].se-1);
ptr++;
}
// if (i <= 3){
// for (ll j = 0;j <= 3;j ++){
// cout<<get(tree[i],j)<<' ';
// }
// cout<<'\n';
// }
}
}
ll b[MAXM];
ll m;
int can(int M, int K[]) {
m=M;
for (ll i = 0;i < m;i ++)b[i] = K[i];
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> pre(sz(c));
for (ll i = 1;i < sz(c);i ++){
pre[i] = query(c[i-1].fi,c[i].fi);
}
for (ll i = 0;i < sz(c);i ++){
ll cur = query(0,c[i].fi);
ll sum = c[i].fi*c[i].se;
if (cur < sum)return 0;
for (ll j = i + 1;j < sz(c);j ++){
cur += pre[i];
sum += c[j].fi * c[j].se;
if (cur < sum)return 0;
}
}
return 1;
}
