#include "teams.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define MOD 1000000007
#define M 20000000
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;
struct ask {
int suf;
int l,r;
};
int D;
int tot;
int show[500005];
int P[M],l[M],r[M];
vector<int> root;
ii query(int node,int alt,int bas,int son,int x,int y,ll need) {
if(bas>y || son<x) return {0,-1};
if(bas>=x && son<=y) {
if(P[node]-P[alt]<need) return {P[node]-P[alt],-1};
if(bas==son) return {1,bas};
}
ii res=query(l[node],l[alt],bas,orta,x,y,need);
if(res.nd==-1) {
need-=res.st;
ii res2=query(r[node],r[alt],orta+1,son,x,y,need);
if(res2.nd!=-1) return res2;
res.st+=res2.st;
}
return res;
}
int get(int node,int alt,int bas,int son,int x,int y) {
if(x>y) return 0;
if(bas>y || son<x) return 0;
if(bas>=x && son<=y) return P[node]-P[alt];
return get(l[node],l[alt],bas,orta,x,y)+get(r[node],r[alt],orta+1,son,x,y);
}
void up(int& node,int& alt,int bas,int son,int pos) {
if(node==alt) {
node=++tot;
}
if(bas==pos && son==pos) {
P[node]=P[alt]+1;
return ;
}
if(!r[node]) r[node]=r[alt];
if(!l[node]) l[node]=l[alt];
if(orta>=pos) {
up(l[node],l[alt],bas,orta,pos);
}
else {
up(r[node],r[alt],orta+1,son,pos);
}
P[node]=P[l[node]]+P[r[node]];
}
void build(int& node,int bas,int son) {
node=++tot;
if(bas==son) {
P[node]=0;
return ;
}
build(l[node],bas,orta);
build(r[node],orta+1,son);
P[node]=P[l[node]]+P[r[node]];
}
void init(int N, int A[], int B[]) {
vector<vector<int>> le=vector<vector<int>>(N+1);
root=vector<int>(N+1);
vector<ii> cmp;
for(int i=0;i<N;i++) {
cmp.pb({B[i],i});
}
for(int i=1;i<=N;i++) {
cmp.pb({i,-1});
}
sort(all(cmp),[&](ii a,ii b) {
if(a.st<b.st) return true;
if(a.st>b.st) return false;
if(a.nd==-1) return true;
if(b.nd==-1) return false;
return (A[a.nd]==A[b.nd]?a.nd<b.nd:A[a.nd]<A[b.nd]);
});
for(int i=0;i<sz(cmp);i++) {
//cerr<<cmp[i].st<<" "<<cmp[i].nd<<"\n";
if(cmp[i].nd==-1) {
show[cmp[i].st]=i+1;
}
else {
B[cmp[i].nd]=i+1;
}
}
for(int i=0;i<N;i++) {
le[A[i]].pb(B[i]);
}
D=sz(cmp);
build(root[0],1,D);
for(int i=1;i<=N;i++) {
root[i]=root[i-1];
//cerr<<"PUSHED\n";
for(int x:le[i]) {
// cerr<<i<<" "<<x<<"\n";
up(root[i],root[i-1],1,D,x);
}
// cerr<<"PUSHED\n";
}
}
int can(int SZ, int K[]) {
sort(K,K+SZ);
vector<ask> s;
s.pb({D+1,0,0});
for(int i=0;i<SZ;i++) {
ll need=K[i];
while(i+1<SZ && K[i]==K[i+1]) i++,need+=K[i];
ask cur={show[K[i]],s.back().r+1,K[i]};
// cerr<<"K[I] : "<<K[i]<<"\n";
// cerr<<"need : "<<need<<"\n";
while(s.back().suf<=cur.suf) {
cur.l=s.back().l;
s.ppb();
}
s.pb(cur);
bool flag=0;
while(sz(s)>1) {
ask last=s.back();
s.ppb();
ask last2=s.back();
s.ppb();
int cnt=get(root[last.r],root[last.l-1],1,D,last.suf,last2.suf-1);
// cerr<<"CNT IS : "<<cnt<<"\n";
// cerr<<"l r is : "<<last.suf<<" "<<last2.suf-1<<"\n";
if(cnt>need) {
flag=1;
s.pb(last2);
s.pb(last);
break ;
}
else {
need-=cnt;
last2.r=last.r;
s.pb(last2);
}
if(need==0) break ;
}
if(!need) continue ;
if(!flag) {
/*cerr<<"--------------\n";*/return 0;}
ask last=s.back();
s.ppb();
ii res=query(root[last.r],root[last.l-1],1,D,last.suf,s.back().suf-1,need);
//cerr<<"res.nd : "<<res.nd<<"\n";
last.suf=res.nd+1;
s.pb(last);
}
//cerr<<"--------------\n";
return 1;
}
