#include <bits/stdc++.h>
#define pb push_back
#define M 524288
using namespace std;
struct r2d{
vector<int> tree[M*2];
void put(int x,int y){
y += M;
while(y){
//printf("put %6d\n",y);
tree[y].pb(x);
y>>=1;
}
}
inline int get(vector<int>& a,int f,int t){
if(max(int(upper_bound(a.begin(), a.end(), t) -
lower_bound(a.begin(), a.end(), f)), 0) > 0){
}
return max(int(upper_bound(a.begin(), a.end(), t) -
lower_bound(a.begin(), a.end(), f)), 0);
}
int rectsum(int l,int r,int d,int u){
d+=M; u+=M;
int ret=0;
while(d<=u){
if(d&1) ret+=get(tree[d++], l, r);
if(!(u&1)) ret+=get(tree[u--], l, r);
d>>=1; u>>=1;
}
return ret;
}
int pick_y(int l,int r,int d,int u,int sum_target,int boundary){
int pos=1, myl=0, myr=M-1, mid;
sum_target += rectsum(l, r, 0, d-1);
int making_sum=0;
while(pos<M){
mid=(myl+myr)/2;
pos*=2;
int cur_sum = get(tree[pos], l, r);
if(myl<=u && u<=mid) cur_sum += boundary;
if(making_sum + cur_sum < sum_target){
myl=mid+1;
making_sum += cur_sum;
} else {
myr=mid;
}
}
return myl;
}
} seg2d;
int n;
typedef pair<int,int> pp;
vector<pp> pts;
void init(int N, int A[], int B[])
{
n=N;
for(int i=0;i<n;++i){
pts.pb({A[i], B[i]});
}
sort(pts.begin(), pts.end());
for(int i=0; i<n; ++i) seg2d.put(pts[i].first, pts[i].second);
}
typedef pair<pp,int> pyo;
stack<pyo> stk;
int can(int m, int q[])
{
while(stk.size()) stk.pop();
stk.push({{0,500000},0});
sort(q, q+m);
for(int i=0; i<m; ++i){
int x=q[i];
int lasty=x-1;
int left=x;
while(true){
if(stk.size()==0) return false;
pyo a=stk.top();
//printf("Querying: %d,%d / %d,%d\n",a.first.first+1, x, lasty+1, a.first.second);
int that = a.second +
seg2d.rectsum(a.first.first + 1, x, lasty+1, a.first.second);
//printf("That's %d\n",that);
if(that >= left){
//puts("enough");
int y = seg2d.pick_y(a.first.first+1, x, lasty+1, a.first.second, left, a.second);
stk.push({{x, y}, seg2d.rectsum(a.first.first+1, x, lasty+1, y) - left});
break;
} else {
//puts("I'm hungry");
left -= that;
lasty = a.first.second;
stk.pop();
}
}
}
return true;
}
