#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5e5;
struct Point
{
int X, Y;
bool operator < (const Point &p) const { return pii(X, Y)<pii(p.X, p.Y); }
};
struct Node
{
int val;
Node *lc, *rc;
Node() : lc(NULL), rc(NULL), val(0) {}
};
void makeTree(Node *node, int tl, int tr)
{
if(tl==tr) return;
int mid=tl+tr>>1;
node->lc=new Node();
node->rc=new Node();
makeTree(node->lc, tl, mid);
makeTree(node->rc, mid+1, tr);
}
Node *addTree(Node *node, int tl, int tr, int pos)
{
if(pos<tl || tr<pos) return node;
Node *ret=new Node();
if(tl==tr)
{
ret->val=node->val+1;
return ret;
}
int mid=tl+tr>>1;
ret->lc=addTree(node->lc, tl, mid, pos);
ret->rc=addTree(node->rc, mid+1, tr, pos);
ret->val=ret->lc->val+ret->rc->val;
return ret;
}
int query(Node *nodel, Node *noder, int tl, int tr, int l, int r)
{
if(l<=tl && tr<=r) return noder->val-nodel->val;
if(r<tl || tr<l) return 0;
int mid=tl+tr>>1;
return query(nodel->lc, noder->lc, tl, mid, l, r)+query(nodel->rc, noder->rc, mid+1, tr, l, r);
}
Node *tree[MAXN+10];
int N;
Point A[MAXN+10], B[MAXN+10];
int xval[MAXN+10], yval[MAXN+10];
int xcomp[MAXN+10], ycomp[MAXN+10];
int query(int xl, int xr, int yl, int yr)
{
int x=query(tree[xl], tree[xr], 0, N+1, yl, yr);
//printf("%d %d %d %d : %d\n", xl, xr, yl, yr, x);
return x;
}
int M, K[MAXN+10];
void init(int _N, int _A[], int _B[])
{
int i, j;
N=_N; for(i=1; i<=N; i++) A[i]={_A[i-1], _B[i-1]};
sort(A+1, A+N+1);
vector<pii> V;
for(i=1; i<=N; i++) V.push_back({A[i].Y, i});
sort(V.begin(), V.end());
for(i=0; i<V.size(); i++) B[V[i].second].Y=i+1;
for(i=1; i<=N; i++) B[i].X=i;
tree[0]=new Node();
makeTree(tree[0], 0, N+1);
for(i=1; i<=N; i++) tree[i]=addTree(tree[i-1], 0, N+1, B[i].Y);
for(i=1; i<=N; i++) xval[B[i].X]=A[i].X;
for(i=1; i<=N; i++) yval[B[i].Y]=A[i].Y;
for(i=1; i<=N; i++) xcomp[i]=upper_bound(xval+1, xval+N+1, i)-xval-1;
for(i=1; i<=N; i++) ycomp[i]=lower_bound(yval+1, yval+N+1, i)-yval;
//for(i=1; i<=N; i++) printf("%d ", xcomp[i]); printf("\n");
//for(i=1; i<=N; i++) printf("%d ", ycomp[i]); printf("\n");
}
int can(int _M, int _K[])
{
int i, j;
M=_M; for(i=1; i<=M; i++) K[i]=_K[i-1];
sort(K+1, K+M+1);
vector<Point> S;
S.push_back({0, N+1});
for(i=1; i<=M; i++)
{
int todo=K[i];
Point now={xcomp[K[i]], ycomp[K[i]]};
while(!S.empty() && S.back().Y<now.Y) S.pop_back();
while(1)
{
//printf("!%d %d\n", now.X, now.Y);
if(S.empty()) return 0;
Point T=S.back();
int lo=now.Y-1, hi=T.Y;
while(lo+1<hi)
{
int mid=lo+hi>>1;
int p=query(T.X, now.X, now.Y, mid);
if(p<todo) lo=mid;
else hi=mid;
}
todo-=query(T.X, now.X, now.Y, hi);
if(todo==0)
{
if(lo==T.Y) S.pop_back();
//printf("WTF %d\n", hi);
S.push_back({now.X, hi});
break;
}
now.Y=T.Y+1;
S.pop_back();
}
//for(auto it : S) printf("%d %d\n", it.X, it.Y);
//printf("\n");
}
return 1;
}
