#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define ull unsigned ll
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
//#include "teams.h"
const ll siz = 500005;
vector<ii>arr;
ll R[siz];
ll n;
vector<ll>seg[4 * siz];
void build(ll s,ll e,ll idx){
if(s == e){
seg[idx].pb(arr[s-1].S);
return;
}
ll mid = (s + e) / 2;
build(s,mid,idx * 2);
build(mid+1,e,idx * 2 + 1);
ll p1 = 0,p2 = 0;
while(p1 < seg[idx * 2].size() && p2 < seg[idx * 2 + 1].size()){
if(p1 == seg[idx * 2].size()){
seg[idx].pb(seg[idx * 2 + 1][p2]);
p2++;
}
else if(p2 == seg[idx *2 + 1].size()){
seg[idx].pb(seg[idx * 2][p1]);
p1++;
}
else{
if(seg[idx * 2][p1] < seg[idx * 2 + 1][p2]){
seg[idx].pb(seg[idx * 2][p1]);
p1++;
}
else{
seg[idx].pb(seg[idx * 2 + 1][p2]);
p2++;
}
}
}
}
ll query(ll s,ll e,ll qs,ll qe,ll idx,ll k){
if(qs <= s && e <= qe){
return upper_bound(all(seg[idx]),k) - seg[idx].begin();
}
if(s > qe || qs > e){
return 0;
}
ll mid = (s + e) / 2;
ll a = query(s,mid,qs,qe,idx * 2,k);
ll b = query(mid+1,e,qs,qe,idx * 2 + 1,k);
return a + b;
}
void init(int N, int A[], int B[]){
n = N;
f(i,0,n){
arr.pb(ii(A[i],B[i]));
}
sort(all(arr));
ll pos = 1;
for(auto x:arr){
R[x.F] = pos;
pos++;
}
build(1,n,1);
}
int can(int M, int K[]) {
bool ok = true;
ll sum = 0;
vector<ii>ex;
f(i,0,M){
sum += K[i];
if(i > 0 && K[i] == K[i-1]){
ex.back().S++;
}
else{
ex.pb(ii(K[i],1));
}
}
if(sum > n){
return 0;
}
ll siz = ex.size();
ll posa[siz] = {0};
ll l = 1;
ll j = 0;
for(auto x:ex){
ll ev = 0;
ll r = R[x.F];
f(i,0,siz){
ll v = query(1,n,l,r,1,ex[i].F);
posa[i] += v - ev;
ev = v;
}
ll em = x.S * x.F;
f(i,j,siz){
ll E = min(posa[i],em);
em -= E;
posa[i] -= E;
}
if(em > 0){
ok = 0;
break;
}
l = r + 1;
j++;
}
return ok;
}
