#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
refs:
edi
*/
const int MOD = 1e9 + 7;
const int N = 5e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#include "teams.h"
struct wavelet_tree{
struct node{
node *l, *r;
vector<int> b;
};
node* root;
int siz;
wavelet_tree(){
}
node* build(vector<int> &a, vector<int> inds, int l, int r){
if(l > r) return NULL;
int mid = (l+r) >> 1;
vector<int> b(sz(inds)+1);
vector<int> la,ra;
rep(i,sz(inds)){
int x = a[inds[i]];
b[i+1] = b[i]+(x <= mid);
if(x <= mid){
la.pb(inds[i]);
}
else{
ra.pb(inds[i]);
}
}
node* curr = new node();
curr->b = b;
if(l != r){
curr->l = build(a,la,l,mid);
curr->r = build(a,ra,mid+1,r);
}
return curr;
}
void build(vector<int> &a, int mx_siz){
siz = mx_siz;
vector<int> inds;
rep(i,sz(a)) inds.pb(i);
root = build(a,inds,0,siz);
}
int get_cnt(node* u, int lx, int rx, int l, int r, int vl, int vr){
if(!u) return 0;
if(l > r) return 0;
if(lx > vr or rx < vl) return 0;
if(lx >= vl and rx <= vr) return r-l+1;
int mid = (lx+rx) >> 1;
auto &b = u->b;
int res = 0;
res += get_cnt(u->l,lx,mid,b[l-1]+1,b[r],vl,vr);
res += get_cnt(u->r,mid+1,rx,l-b[l-1],r-b[r],vl,vr);
return res;
}
int get_cnt(int l, int r, int vl, int vr){
return get_cnt(root,0,siz,l+1,r+1,vl,vr);
}
};
int n;
vector<pii> a;
wavelet_tree wt;
vector<int> lb;
void init(int n_, int A[], int B[]) {
n = n_;
rep(i,n) a.pb({A[i],B[i]});
sort(all(a));
lb = vector<int>(n+5,n);
rep(i,n) amin(lb[a[i].ff],i);
rev(i,n,0) amin(lb[i],lb[i+1]);
vector<int> b;
rep(i,n) b.pb(a[i].ss);
wt.build(b,n+1);
}
int can(int m, int K[]) {
int sum = 0;
rep(i,m){
sum += K[i];
if(sum > n){
return 0;
}
}
sort(K,K+m);
vector<pii> c;
c.pb({K[0],K[0]});
rep1(i,m-1){
if(K[i] == K[i-1]){
c.back().ss += K[i];
}
else{
c.pb({K[i],K[i]});
}
}
auto get = [&](int mnl, int mxl, int mnr){
return wt.get_cnt(lb[mnl],lb[mxl+1]-1,mnr,n);
};
c.insert(c.begin(),{0,0});
m = sz(c);
set<int> st;
st.insert(0);
vector<int> leave[m];
vector<int> dp(m,inf1);
dp[0] = 0;
// auto odp = dp;
rep1(i,m-1){
while(!leave[i].empty()){
ll j = leave[i].back();
leave[i].pop_back();
if(!st.count(j)) conts;
st.erase(j);
auto it = st.upper_bound(j);
if(it != st.end() and it != st.begin()){
int x = *prev(it), y = *it;
int val = dp[y]-dp[x];
int lo = i, hi = m-1;
int pos = -1;
while(lo <= hi){
int mid = (lo+hi) >> 1;
if(val >= get(c[x].ff+1,c[y].ff,c[mid].ff)){
pos = mid;
hi = mid-1;
}
else{
lo = mid+1;
}
}
if(pos != -1){
leave[pos].pb(y);
}
}
}
{
int j = *st.rbegin();
dp[i] = dp[j]+get(c[j].ff+1,c[i].ff,c[i].ff)-c[i].ss;
}
st.insert(i);
auto it = st.find(i);
{
int x = *prev(it), y = *it;
int val = dp[y]-dp[x];
int lo = i+1, hi = m-1;
int pos = -1;
while(lo <= hi){
int mid = (lo+hi) >> 1;
if(val >= get(c[x].ff+1,c[y].ff,c[mid].ff)){
pos = mid;
hi = mid-1;
}
else{
lo = mid+1;
}
}
if(pos != -1){
leave[pos].pb(y);
}
}
// rep(j,i){
// amin(odp[i],odp[j]+get(c[j].ff+1,c[i].ff,c[i].ff));
// }
// odp[i] -= c[i].ss;
}
// debug(dp);
// debug(odp);
// assert(dp == odp);
int mn = *min_element(all(dp));
return mn >= 0;
}
