//#include "teams.h"
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
const int NN=500000;
int f[NN+11];
struct Node{
Node *left=nullptr, *right=nullptr;
int cnt=0;
Node(){}
Node (Node *node) : left(node->left), right(node->right), cnt(node->cnt){}
void extend(){
if(!left){
left = new Node();
right = new Node();
}
}
void add(int y, int l=0, int r=NN){
// cout<<l<<" "<<r<<" "<<y<<endl;
if(l+1==r){
cnt+=1;
return;
}
extend();
int mid=l+r>>1;
if(y<mid){
left = new Node(left);
left -> add(y, l, mid);
}else{
right = new Node(right);
right -> add(y, mid, r);
}
cnt = left->cnt + right->cnt;
}
int get(int L, int R, int l=0, int r=NN){
// cout<<"[L, R]: "<<L<<" "<<R<<endl;
// cout<<"AAA"<<endl;
// cout<<"[l, r, cnt]: "<<l<<" "<<r<<" "<<cnt<<endl;
if(l>=R || r<=L)return 0;
if(l>=L && r<=R){
// cout<<endl<<"[L, R, l, r, cnt]: "<<L<<" "<<R<<" "<<l<<" "<<r<<" "<<cnt<<endl;
return cnt;
}
// cout<<"![L, R]: "<<L<<" "<<R<<endl;
// cout<<"!AAA"<<endl;
// cout<<"![l, r, cnt]: "<<l<<" "<<r<<" "<<cnt<<endl;
extend();
int mid=l+r>>1;
return left->get(L, R, l, mid) + right->get(L, R, mid, r);
}
} node;
struct PST{
int sz;
vector<Node*> r;
PST(){ sz=1; r.push_back(new Node()); }
void add(int x, int y){
while(sz<=x){
r.push_back(new Node(r[sz-1]));
sz++;
}
// cout<<r.size()<<" "<<sz<<endl;
r[sz-1]->add(y);
// cout<<"BBB"<<endl;
}
int get1(int xl, int xr, int y_min, int y_max){
// cout<<endl<<"AAS"<<xr<<" "<<xl<<" "<<r[xr]->get(y_min, y_max)- r[max(0, xl-1)]->get(y_min, y_max)<<endl;
return r[xr]->get(y_min, y_max) - r[max(0, xl-1)]->get(y_min, y_max);
}
int get2_1(Node *xl, Node *xr, int wcnt, int l=0, int r=NN){
// cout<<"CCC "<<wcnt<<endl;
if(l + 1 == r){
if(wcnt > xr->cnt - xl->cnt){
return 1000000000;
}
return r;
}
xl->extend();
xr->extend();
int cnt = xr->left->cnt - xl->left->cnt, mid=l+r>>1;
return (cnt>=wcnt) ? get2_1(xl->left, xr->left, wcnt, l, mid)
: get2_1(xl->right, xr->right, wcnt - cnt, mid, r);
}
int get2(int xl, int xr, int y_min, int cnt){
// cout<<"DDD "<<xl<<" "<<xr<<" "<<y_min<<" "<<get1(xl, xr, 0, y_min)<<endl;
return get2_1(r[max(0, xl-1)], r[xr], cnt+get1(xl, xr, 0, y_min));
}
};
PST *pst=new PST();
void init(int N, int A[], int B[]) {
vector<array<int, 2>> v(N);
for (int i=0; i<N; i++){
v[i]={B[i], A[i]};
}
// cout<<N<<endl;
sort(all(v));
int o=1;
int prev_y=0, new_y=0, Y=0;
for (auto &[y,x] : v){
if(y==prev_y){
++new_y;
y=new_y;
}else{
prev_y=y;
++new_y;
while(Y<y){
Y++;
f[Y]=new_y;
}
y=new_y;
}
}
// for (auto &[y,x] : v){
// y+=o;
// if(f[y-o]==y-o)f[y-o]=y;
// fr[y-o]=y;
// o++;
// }
int X=f[Y]+1;
while(Y<NN){
Y++;
f[Y]=X;
}
// cout<<"[f]: ";
// for (int i=0; i<10; i++){
// cout<<f[i]<<" ";
// }
// cout<<endl;
// cout<<"AAA"<<endl;
for (auto &[y,x]:v)swap(x,y);
sort(all(v));
// cout<<"[y_x]: ";
// for (auto [x,y]:v){
// cout<<x<<"_"<<y<<" ";
// }
// cout<<endl;
for (auto [x,y] : v){
pst->add(x,y);
}
while(pst->sz<NN-1){
pst->r.push_back(new Node(pst->r[pst->sz-1]));
pst->sz++;
}
}
int can(int M, int K[]) {
// cout<<M<<endl;
sort(K, K+M);
array<int, 3> s[M+5];
int o=0;
// xl xr y_min
s[o++] = {0, 0, f[NN-1]};
for (int i=0; i<M; i++){
int k=K[i];
int xl=s[o-1][1]+1, xr=k, y_min=f[k], y_max=s[o-1][2], cnt=k, c;
// if(i && k==K[i-1]){
// if(o==1){
// return 0;
// }
// xl=s[o-1][0], xr=s[o-1][1], y_min=s[o-1][2], y_max=s[o-2][2];
// }
// cout<<"DDD"<<pst->get1(xl, xr, y_min, y_max)<<endl;
while(o>1 && cnt && (c=pst->get1(xl, xr, y_min, y_max)) <= cnt){
// cout<<"[k, xl, xr, y_min, y_max, cnt]: ";
// cout<<k<<" "<<xl<<" "<<xr<<" "<<y_min<<" "<<y_max<<" "<<cnt<<endl;
// cout<<"[c, o]: "<<c<<" "<<o<<endl;
cnt-=c;
o--;
xl=s[o][0];
y_min=max(y_min, y_max);
y_max=s[o-1][2];
}
// cout<<k<<" "<<cnt<<" "<<xr<<" "<<xl<<endl;
if(cnt){
// cout<<"AAA"<<xr<<" "<<xl<<endl;
// cout<<"[k, xl, xr, y_min, y_max, cnt]: ";
// cout<<k<<" "<<xl<<" "<<xr<<" "<<y_min<<" "<<y_max<<" "<<cnt<<endl;
y_min = pst->get2(xl, xr, y_min, cnt);
// cout<<y_min<<endl;
if(y_min>NN){
return 0;
}
}
s[o++]={xl, xr, y_min};
// cout<<"AQA "<<s[o-1][2]<<endl;
}
return 1;
}
