#include<bits/stdc++.h>
using namespace std;
#include "teams.h"
#define mx 200005
#define tm (tl+tr >> 1)
int s[mx*30],L[mx*30],R[mx*30],root[mx],nw;
int up(int v, int tl, int tr, int i){
if(tl > i || tr < i) return v;
int w = ++nw;
if(tl < tr){
L[w] = up(L[v],tl,tm,i);
R[w] = up(R[v],tm+1,tr,i);
}
s[w] = s[v]+1;
return w;
}
int qry(int a, int b, int tl, int tr, int l, int r){
if(tl > r || tr < l) return 0;
if(tl >= l && tr <= r) return s[a]-s[b];
return qry(L[a],L[b],tl,tm,l,r) + qry(R[a],R[b],tm+1,tr,l,r);
}
#define mp make_pair
#define st first
#define nd second
int n;
int can(int m, int *K){
int t,i,l,md,r,x,y,z,las,req,ex;
stack < pair < int , pair<int,int> > > S;
S.push(mp(0,mp(mx,0)));
sort(K , K+m);
for(i=0;i<m;i++){
las = req = x = K[i];
ex = 0;
for(;;){
y = S.top().st;
z = S.top().nd.st;
if(z < las){
S.pop();
continue;
}
if(z == las){
ex += S.top().nd.nd;
S.pop();
continue;
}
l = las;
r = n+1;
for(; l<r ;){
md = l+r >> 1;
if(qry(root[x],root[y],1,n,las,md)-ex >= req) r = md;
else l = md+1;
}
if(l >= (t = S.top().nd.st)){
req -= qry(root[x],root[y],1,n,las,t-1) - ex;
las = t;
ex = S.top().nd.nd;
S.pop();
continue;
}
else{
//cout << x << " " << y << " " << req <<" " << ex << " zz\n";
req -= qry(root[x],root[y],1,n,las,l)-ex;
//cout << i << " " << las << " " << l << " " << req << " ss\n";
if(req > 0) return 0;
ex = req + qry(root[x],root[y],1,n,l,l);
S.push(mp(x,mp(l,ex)));
break;
}
}
}
return 1;
}
vector < int > V[mx];
void init(int ss, int *a, int *b){
n = ss;
int i,j,p=0;
for(i=0;i<n;i++) V[ a[i] ].push_back(b[i]);
for(i=1;i<=n;i++){
for(j=0;j<V[i].size();j++)
p = up(p,1,n,V[i][j]);
root[i] = p;
}
}
