#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct item * pitem;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
struct item {
pitem l=nullptr, r=nullptr;
int x=0;
};
const int LIM=5e5+7;
pitem roots[LIM];
pair<int,int>T[LIM];
int n, N=1;
void build(pitem v, int l, int r) {
if(l==r) return;
v->l=new item();
v->r=new item();
int mid=(l+r)/2;
build(v->l, l, mid);
build(v->r, mid+1, r);
}
pitem upd(pitem v, int l, int r, int a) {
if(r<a || a<l) return v;
pitem x=new item();
x->x=v->x+1;
if(l==r) {
x->l=v->r;
x->r=v->r;
return x;
}
int mid=(l+r)/2;
x->l=upd(v->l, l, mid, a);
x->r=upd(v->r, mid+1, r, a);
x->x=x->l->x+x->r->x;
return x;
}
int cnt(pitem v, int l, int r, int a, int b) {
if(r<a || b<l) return 0;
if(a<=l && r<=b) return v->x;
int mid=(l+r)/2;
return cnt(v->l, l, mid, a, b)+cnt(v->r, mid+1, r, a, b);
}
int kwad(int l, int r, int a, int b) {
return cnt(roots[r+1], 0, N-1, a, b)-cnt(roots[l], 0, N-1, a, b);
}
void init(int _N, int A[], int B[]) {
n=_N;
while(N<=n) N*=2;
rep(i, n) T[i]={B[i], A[i]};
sort(T, T+n);
T[n]={n+1, 0};
roots[0]=new item();
build(roots[0], 0, N-1);
rep(i, n+1) roots[i+1]=upd(roots[i], 0, N-1, T[i].nd);
}
int znajdz(int x) {
int po=0, ko=n;
while(po<ko) {
int sr=(po+ko)/2;
if(T[sr].st<x) po=sr+1; else ko=sr;
}
return po;
}
int can(int m, int K[]) {
sort(K, K+m);
int sum=0;
rep(i, m) {
sum+=K[i];
if(sum>n) return 0;
}
vector<pair<int,int>>P;
P.pb({0, n});
vector<pair<int,int>>Q;
Q.pb({K[0], K[0]});
for(int i=1; i<m; ++i) if(K[i]!=Q.back().st) Q.pb({K[i], K[i]}); else Q[Q.size()-1].nd+=K[i];
m=Q.size();
rep(i, m) {
int x=Q[i].nd, a=znajdz(Q[i].st);
if(a==n) return 0;
while(P.back().nd<a) P.pop_back();
while(P.size()>0) {
int c=kwad(a, P.back().nd, P.back().st+1, Q[i].st);
if(c>=x) break;
x-=c;
a=P.back().nd+1;
P.pop_back();
}
if(P.size()==0) return 0;
int po=a, ko=n;
int o=cnt(roots[a], 0, N-1, P.back().st+1, Q[i].st);
while(po<ko) {
int sr=(po+ko)/2;
if(cnt(roots[sr+1], 0, N-1, P.back().st+1, Q[i].st)-o<x) po=sr+1; else ko=sr;
}
P.pb({Q[i].st, po});
}
return 1;
}
