#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long int lld;
typedef pair<lld,lld> pll;
#define MAXN 500000
#define SQ 250001000001
#define DEBUG 0
/*
4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1
*/
struct ST
{
ST *L,*R;
vector<lld> v;
lld l,r;
};
typedef ST *tree;
void ext(tree n)
{
if(!n->L)
{
n->L=new ST();
n->R=new ST();
lld mid=(n->l+n->r)/2;
n->L->l=n->l;
n->L->r=mid;
n->R->l=mid+1;
n->R->r=n->r;
}
}
void upd(tree n,lld pos, lld val)
{
//cout<<n->l<<" "<<n->r<<endl;
if(pos<n->l || n->r<pos)return;
//cout<<n->l<<" "<<n->r<<endl;
n->v.push_back(val);
if(n->l==n->r)return;
ext(n);
upd(n->L,pos,val);
upd(n->R,pos,val);
}
int Q(tree n,lld l, lld r, int e)
{
if(!n)return 0;
if(r<n->l || n->r<l)return 0;
if(l<=n->l && n->r<=r){
int lo,hi;
lo=-1;
hi=n->v.size();
while(hi-lo>1){
int mid=(lo+hi)/2;
if(n->v[mid]>e)hi=mid;
else lo=mid;
}
//cout<<hi<<" "<<e<<endl;
return hi;
}
return Q(n->L,l,r,e)+Q(n->R,l,r,e);
}
int query(tree n,lld l, lld r, int s, int e){
return Q(n,l,r,e)-Q(n,l,r,s-1);
}
lld nav(tree n, int s, int e, int val){
ext(n);
//cout<<n->l<<" "<<n->r<<" "<<val<<endl;
if(n->l==n->r){
if(val>0)return n->r+1;
return n->r;
}
if(!n->L){
return n->r+1;
}
int ans=query(n->L,n->L->l,n->L->r,s,e);
//cout<<ans<<endl;
if(ans>val){
return nav(n->L,s,e,val);
}
return nav(n->R,s,e,val-ans);
}
pair<lld,lld> arr[MAXN];
int n;
tree T;
void init(int N, int A[], int B[])
{
n=N;
for(int i=0; i<n; i++)
{
arr[i]=pll(A[i],B[i]);
}
sort(arr,arr+n);
T=new ST();
T->l=0;
T->r=SQ;
//cout<<T->r<<endl;
//S->print(0,n,1);
//cout<<S->q(2,4,2,3);
for(int i=0; i<n; i++)
{
//cout<<arr[i].second<<endl;
if(DEBUG==0){
arr[i].second=arr[i].second*MAXN+i+1;
}
//cout<<arr[i].second<<" "<<i<<endl;
upd(T,arr[i].second,i);
}
//cout<<nav(T,0,2,3)<<endl;
}
int can(int M, int K[])
{
sort(K,K+M);
if(DEBUG==1){
int pnt=0;
priority_queue<int>pq;
for(int i=0;i<M;i++){
while(pnt<n && arr[pnt].first<=K[i]){
pq.push(-arr[pnt].second);
pnt++;
}
while(-pq.top()<K[i]){
if(pq.empty())return 0;
pq.pop();
}
for(int j=0;j<K[i];j++){
if(pq.empty())return 0;
pq.pop();
}
}return 1;
}
stack<pll>s;
for(int i=0;i<M;i++){
int lo,hi;
lo=-1;
hi=n;
while(hi-lo>1){
int mid=(hi+lo)/2;
if(arr[mid].first<=K[i]){
lo=mid;
}else hi=mid;
}
//cout<<lo<<endl;
//cout<<arr[hi].second/MAXN<<endl;
lld H=MAXN*(lld)K[i];
while(!s.empty() && s.top().second<=H){
s.pop();
}
int Group=K[i];
//cout<<H<<endl;
//cout<<H<<" B"<<s.size()<<endl;
while(!s.empty() && query(T,H,s.top().second-1,s.top().first+1,lo)<=Group){
Group-=query(T,H,s.top().second-1,s.top().first+1,lo);
H=s.top().second;
s.pop();
}
//cout<<s.size()<<" A "<<H<<endl;
if(s.empty()){
//cout<<Q(T,0,SQ,lo)<<"Q"<<endl;
if(query(T,H,SQ,0,lo)<Group){
return 0;
}
H=nav(T,0,lo,Group+query(T,0,H-1,0,lo));
}else{
H=nav(T,s.top().first+1,lo,Group+query(T,0,H-1,s.top().first+1,lo));
}
s.push(pll(lo,H));
//cout<<lo<<" "<<H<<endl;
}
return 1;
}
