#include "teams.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second.first
#define remain second.second
using namespace std;
const int N=2e5+1,mod=1e9+7;
struct nd{
ll val;
nd *l,*r;
nd(ll value = 0,nd *left = NULL, nd *right = NULL){
l = left,r = right,val = value;
}
nd(nd *node){
l = node -> l,r = node -> r,val = node -> val;
}
};
int n;
pair<int,int> rng[N];
int l[N],x[N];
vector<nd*>v(n+1);
void update(int idx,nd *node,int l = 1,int r = n){
if(l == r){
node -> val ++;
return;
}
int mid = (l + r)/2;
if(node -> l == NULL)
node -> l = new nd();
if(node -> r == NULL)
node -> r = new nd();
if(idx <= mid){
node -> l = new nd(node -> l);
update(idx,node -> l,l,mid);
}
else{
node -> r = new nd(node -> r);
update(idx,node -> r,mid+1,r);
}
node -> val = (node -> l -> val) + (node -> r -> val);
}
ll get(int ql, int qr,nd *node,nd *minus = NULL,int l = 1,int r = n){
if(ql>qr || qr>n){
//cout<<"wal: "<<ql<<" "<<qr<<"\n";
return 0;
}
if(minus == NULL){
minus = new nd();
minus -> l = minus, minus -> r = minus;
}
if(r < ql || qr < l)
return 0;
if(ql <= l && r <= qr)
return (node -> val) - (minus -> val);
int mid=(l + r)/2;
if(node -> l == NULL)
node -> l = new nd();
if(node -> r == NULL)
node -> r = new nd();
return get(ql,qr,node -> l,minus -> l,l,mid) + get(ql,qr,node -> r,minus -> r,mid + 1,r);
}
void init(int en, int A[], int B[]) {
n=en;
for(int i = 1;i <= n;i++){
rng[i].F = A[i-1],rng[i].second = B[i-1];
}
sort(rng+1,rng+n+1);
v[0] = new nd();
for(int i = 1;i <= n;i++){
l[i] = rng[i].F;
v[i] = new nd(v[i-1]);
update(rng[i].second,v[i]);
}
}
int can(int m, int K[]) {
for(int i = 1;i <= m;i++)
x[i]=K[i-1];
sort(x+1,x + m + 1);
bool ok = 1;
vector<pair<nd*,pair<int,int>>>st;
st.push_back({new nd(),{n,0}});
for(int i = 1;i <= m;i++){
int u = upper_bound(l,l+n+1,x[i])-l-1;
//cout<<"u "<<u<<endl;
nd *root = v[u];
int ans = x[i];
int b = x[i],e = -1;
while(st.size()){
//cout<<b<<" "<<st.back().S;
int gr = get(b,st.back().S,root,st.back().F) + st.back().remain;
//cout<<"get+remain: "<<gr<<endl;
while(b > st.back().S){
st.pop_back();
//cout<<b<<" "<<st.back().S;
gr = get(b,st.back().S,root,st.back().F) + st.back().remain;
}
if(ans <= gr)
break;
ans -= gr;
b = st.back().S+1;
st.pop_back();
}
if(st.size())
e = st.back().S;
else
return 0;
nd *minus = st.back().F;
int last = e,remaining;
while(b <= e){
int mid = (b + e)/2;
ll cur = get(b,mid,root,minus);
if(mid == st.back().S)
cur+=st.back().remain;
if(cur >= ans){
last = mid,e = mid - 1;
remaining = cur - ans;
}
else
b=mid+1;
}
//cout<<"last: "<<last<<" remaining: "<<remaining<<"\n";
if(st.back().S == last && remaining <= st.back().remain)
st.pop_back();
st.push_back({root,{last,remaining}});
}
return 1;
}
