//#include "teams.h"
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
const int NN=1000000, INF=1e6-666;
int fl[1000001], fr[1000001];
struct Node{
Node *left=nullptr, *right=nullptr;
int l, r, cnt;
Node(){}
Node (int l, int r) : l(l), r(r), cnt(0){}
Node (Node *node) : left(node->left), right(node->right), l(node->l), r(node->r), cnt(node->cnt){}
void extend(){
if(!left){
int mid=l+r>>1;
left = new Node(l, mid);
right = new Node(mid, r);
}
}
void add(int y){
// cout<<l<<" "<<r<<" "<<y<<endl;
if(l+1==r){
cnt+=1;
return;
}
extend();
if(y<(l+r>>1)){
left = new Node(left);
left -> add(y);
}else{
right = new Node(right);
right -> add(y);
}
cnt = left->cnt + right->cnt;
}
int get(int L, int R){
// 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();
return left->get(L, R) + right->get(L, R);
}
} node;
struct PST{
int sz;
vector<Node*> r;
PST(){ sz=1; r.push_back(new Node(0, NN)); }
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){
if(xl->l + 1 == xl->r){
if(wcnt > xr->cnt - xl->cnt){
return INF-10;
}
return xl->r;
}
xl->extend();
xr->extend();
int cnt = xr->left->cnt - xl->left->cnt;
return (cnt>=wcnt) ? get2_1(xl->left, xr->left, wcnt)
: get2_1(xl->right, xr->right, wcnt - cnt);
}
int get2(int xl, int xr, int y_min, int cnt){
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<1000000; i++){
fl[i]=fr[i]=i;
}
for (int i=0; i<N; i++){
v[i]={B[i], A[i]};
}
// cout<<N<<endl;
sort(all(v));
int o=1;
for (auto &[y,x] : v){
y+=o;
if(fl[y-o]==y-o)fl[y-o]=y;
fr[y-o]=y;
o++;
}
for (int i=1; i<1000000; i++){
fl[i]=max(fl[i], fr[i-1]+1);
fr[i]=max(fr[i], fr[i-1]+1);
}
// cout<<"[f]: ";
// for (int i=0; i<10; i++){
// cout<<fl[i]<<"_"<<fr[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<1000){
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, fl[INF]};
for (int i=0; i<M; i++){
int k=K[i];
int xl=s[o-1][1]+1, xr=k, y_min=fl[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-1][0];
y_min=y_max;
y_max=s[o-1][2];
}
// cout<<k<<" "<<cnt<<" "<<xr<<" "<<xl<<endl;
if(cnt){
// cout<<"AAA"<<xr<<" "<<xl<<endl;
y_min = pst->get2(xl, xr, y_min, cnt);
// cout<<"BBB"<<endl;
if(y_min>INF-666){
return 0;
}
}
s[o++]={xl, xr, y_min};
// cout<<"AQA "<<s[o-1][2]<<endl;
}
return 1;
}
