#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) {}
};
Node *tree[MAXN+10], *temp;
int N;
Point A[MAXN+10], B[MAXN+10];
int xval[MAXN+10], yval[MAXN+10];
int xcomp[MAXN+10], ycomp[MAXN+10];
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, Node *nodet, int tl, int tr, int l, int r)
{
if(l<=tl && tr<=r) return nodet->val=noder->val-nodel->val;
if(r<tl || tr<l) return nodet->val=0;
int mid=tl+tr>>1;
return nodet->val=query(nodel->lc, noder->lc, nodet->lc, tl, mid, l, r)+query(nodel->rc, noder->rc, nodet->rc, mid+1, tr, l, r);
}
int query(int xl, int xr, int yl, int yr)
{
return query(tree[xl], tree[xr], temp, 0, N+1, yl, yr);
}
int query2(Node *nodel, Node *noder, Node *nodet, int tl, int tr, int l, int r, int k)
{
if(tl==tr) return tl;
if(l<=tl && tr<=r) { nodet->lc->val=noder->lc->val-nodel->lc->val; nodet->rc->val=noder->rc->val-nodel->rc->val; }
int mid=tl+tr>>1;
if(nodet->lc->val<k) return query2(nodel->rc, noder->rc, nodet->rc, mid+1, tr, l, r, k-nodet->lc->val);
else return query2(nodel->lc, noder->lc, nodet->lc, tl, mid, l, r, k);
}
int query2(int xl, int xr, int yl, int yr, int k)
{
query(xl, xr, yl, yr);
return query2(tree[xl], tree[xr], temp, 0, N+1, yl, yr, k);
}
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;
temp=new Node();
makeTree(temp, 0, N+1);
}
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)
{
if(S.empty()) return 0;
Point T=S.back();
int p=min(T.Y, query2(T.X, now.X, now.Y, T.Y, todo));
todo-=query(T.X, now.X, now.Y, p);
//printf("!%d / %d %d / %d %d\n", p, now.X, now.Y, T.X, T.Y);
if(todo==0)
{
if(p==T.Y) S.pop_back();
S.push_back({now.X, p});
break;
}
now.Y=T.Y+1;
S.pop_back();
}
}
return 1;
}
