/// Black lives matter
#include <bits/stdc++.h>
#include "teams.h"
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=5e5+100,M=50;
ll n;
ll roo[N*M];
ll se[N*M];
ll st=1;
ll LL[N*M],RR[N*M];
ll add(ll nod,ll l,ll r,ll id,ll val){
ll NOD=st;
st++;
se[NOD]=se[nod];
LL[NOD]=LL[nod];
RR[NOD]=RR[nod];
if (r-l==1){
se[NOD]+=val;
return NOD;
}
ll mid=(r+l)/2;
if (mid>id) LL[NOD]=add(LL[NOD],l,mid,id,val);
else RR[NOD]=add(RR[NOD],mid,r,id,val);
se[NOD]=se[LL[NOD]]+se[RR[NOD]];
return NOD;
}
ll fin(ll nod1,ll nod2,ll l,ll r,ll val){
if (r-l==1){
if (se[nod2]-se[nod1]<val) return n+1;
return l;
}
ll mid=(r+l)/2;
if (se[LL[nod2]]-se[LL[nod1]]>=val) return fin(LL[nod1],LL[nod2],l,mid,val);
val-=se[LL[nod2]]-se[LL[nod1]];
return fin(RR[nod1],RR[nod2],mid,r,val);
}
ll seg[N*M];
ll L[N*M],R[N*M];
ll ts=1;
ll root[N];
ll upd(ll nod,ll l,ll r,ll id,ll val){
ll NOD=ts;
ts++;
seg[NOD]=seg[nod];
L[NOD]=L[nod];
R[NOD]=R[nod];
if (r-l==1){
seg[NOD]+=val;
return NOD;
}
ll mid=(r+l)/2;
if (mid>id) L[NOD]=upd(L[NOD],l,mid,id,val);
else R[NOD]=upd(R[NOD],mid,r,id,val);
seg[NOD]=seg[L[NOD]]+seg[R[NOD]];
return NOD;
}
ll get(ll nod,ll l,ll r,ll le,ll re){
if (l>=re || le>=r) return 0;
if (l>=le && r<=re) return seg[nod];
ll mid=(r+l)/2;
return get(L[nod],l,mid,le,re)+get(R[nod],mid,r,le,re);
}
vector <int> a,b;
void init(int32_t N, int32_t A[], int32_t B[]) {
n=N;
vector <pii> aa,bb,cc;
b.pb(0);
for (int i=0;i<n;i++){
aa.pb({A[i],B[i]});
b.pb(B[i]);
}
sort(aa.begin(),aa.end());
sort(b.begin(),b.end());
a.pb(0);
for (int i=0;i<aa.size();i++){
a.pb(aa[i].F);
bb.pb({aa[i].S,i+1});
}
sort(bb.begin(),bb.end());
ll last=0;
for (int i=1;i<=n;i++){
ll x=bb[i-1].F,y=bb[i-1].S;
root[i]=upd(root[i-1],1,n+1,y,1);
cc.pb({y,i});
}
sort(cc.begin(),cc.end());
for (int i=1;i<=n;i++){
ll x=cc[i-1].F,y=cc[i-1].S;
roo[i]=add(roo[i-1],1,n+1,y,1);
}
}
ll getk(ll L,ll R,ll k){
/// baste baz
ll x=fin(roo[L-1],roo[R-1],1,n+1,k);
///
return x;
ll l=0,r=n+1;
while(r-l>1){
ll mid=(r+l)/2;
if (get(root[mid],1,n+1,L,R)>=k) r=mid;
else l=mid;
}
if (x!=r) cout <<1/0 << endl;
return r;
}
int32_t can(int32_t M, int32_t K[]) {
vector <pii> m;
sort(K,K+M);
for (int i=0;i<M;i++){
ll s=0;
ll j=i;
while(j<M && K[j]==K[i]) j++,s+=K[i];
m.pb({K[i],s});
i=j-1;
}
vector <pair <int,int> > agh;
agh.pb({0,n});
for (int i=0;i<m.size();i++){
ll x=lower_bound(b.begin(),b.end(),m[i].F)-b.begin()-1;
if (x==n) return 0;
while(agh.size() && agh.back().S<=x) agh.pop_back();
ll z=upper_bound(a.begin(),a.end(),m[i].F)-a.begin();
z--;
if (z==0) return 0;
while(agh.size()){
ll t=agh.back().F;
ll cnt=m[i].S+get(root[x],1,n+1,t+1,z+1);
ll d=getk(t+1,z+1,cnt);
if (d==n+1 && agh.size()==1) return 0;
// if (d==agh.back().S) cout << 1/0;
// cout << d << " ddddddd " << agh.back().S << endl;
if (d<=agh.back().S){
agh.pb({z,d});
break;
}
else{
if (agh.size()==1) return 0;
m[i].S-=get(root[agh.back().S],1,n+1,t+1,z+1)-get(root[x],1,n+1,t+1,z+1);
x=max(x,agh.back().S);
agh.pop_back();
}
}
}
return 1;
}
/*
int32_t A[200],B[200],K[200];
int32_t main(){
ll N,q;
cin >> N;
for(int i=0;i<N;i++){
cin >> A[i] >> B[i];
}
init(N, A, B);
cin >> q;
for(ll i = 0; i < q; i++){
ll m;
cin >> m;
for(ll j = 0; j < m; j++){
cin >> K[j];
}
cout << can(m, K) << " ans" << endl;
}
}
*/
/*
4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1
*/
