#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ar2 = array<int,2>;
const int mxN = (int)5e5+10;
const int mxM = (int)2e5+10;
ar2 v[mxN]; int n;
multiset<int> S;
const int B = sqrt(mxM);
const int mxLg = __lg(mxN)+1;
const int mxSeg = mxN*4*mxLg;
int a[mxN], b[mxN];
int seg[mxSeg], L[mxSeg], R[mxSeg], root[mxSeg];
int segNodes = 1;
int newChild(int p, int v){
int np = ++segNodes;
seg[np] = seg[p]+v;
L[np]=R[np]=0;
return np;
}
int newParent(int lp, int rp){
int np = ++segNodes;
L[np] = lp; R[np] = rp;
seg[np] = seg[lp]+seg[rp];
return np;
}
int upd(int x, int v, int p, int l=1, int r=n){
if(!p) return p;
if(l==r) return newChild(p,v);
int mid = (l+r)/2;
if(!L[p]) L[p]=++segNodes;
if(!R[p]) R[p]=++segNodes;
if(x<=mid) return newParent(upd(x,v,L[p],l,mid),R[p]);
else return newParent(L[p],upd(x,v,R[p],mid+1,r));
}
int query(int i, int j, int p, int l=1, int r=n){
if(!p or i>r or j<l or i>j) return 0;
if(i<=l and r<=j) return seg[p];
int mid = (l+r)/2;
return query(i,j,L[p],l,mid)+query(i,j,R[p],mid+1,r);
}
void init(int N, int A[], int B[]) {
n = N;
for(int i = 0; i < n; i++) a[i]=A[i],b[i]=B[i];
for(int i = 0; i < n; i++) v[i]={a[i],b[i]};
sort(v,v+n,[&](ar2 x, ar2 y){ return x[1]>y[1]; });
int j = 0;
root[n+1] = 1;
for(int i = n; i>=1; i--){
root[i] = root[i+1];
while(j<n and v[j][1]==i)
root[i]=upd(v[j][0],1,root[i]), j++;
}
}
int dp[B+10];
int f(int j, int i, int a[]){
return dp[j]+query(a[j]+1,a[i],root[a[i]]);
}
int can(int m, int a[]) {
sort(a,a+m);
deque<int> dq; dq.clear();
for(int i = 0; i < m; i++){
dp[i] = query(1,a[i],root[a[i]]);
while(sz(dq)>1 and f(end(dp)[-1],i,a) < f(end(dp)[-2],i,a)) dq.pop_back();
if(sz(dq)){
int j = dq[0];
dp[i] = min(dp[i], f(j,i,a));
}
dp[i]-=a[i];
if(dp[i]<0) return 0;
dq.pb(i);
}
return 1;
}
