#include "teams.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define MAXN 10000005
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
int n, m, k, seg[MAXN], sol[MAXN], sag[MAXN], kok[MAXN];
vector < int > g[MAXN];
int up(int k, int bas, int son, int x){
if(bas > x or son < x)
return k;
int yeni = ++m;
seg[yeni] = seg[k] + 1;
if(bas == son)
return yeni;
sol[yeni] = up(sol[k], bas, orta, x);
sag[yeni] = up(sag[k], orta + 1, son, x);
return yeni;
}
int qu(int a, int b, int bas, int son, int x, int y){
if(bas > y or son < x)
return 0;
if(bas >= x and son <= y)
return seg[b] - seg[a];
return qu(sol[a], sol[b], bas, orta, x, y) + qu(sag[a], sag[b], orta + 1, son, x, y);
}
ii bs(int a, int b, int bas, int son, int x){
if(bas == son)
return mp(bas, seg[b] - seg[a] - x);
if(seg[sol[b]] - seg[sol[a]] < x)
return bs(sag[a], sag[b], orta + 1, son, x - (seg[sol[b]] - seg[sol[a]]));
return bs(sol[a], sol[b], bas, orta, x);
}
void init(int nn, int A[], int B[]) {n = nn;
for(int i = 0; i < n; i++)
g[A[i]].pb(B[i]);
for(int i = 1; i <= n; i++){
for(int j = 0; j < g[i].size(); j++)
k = up(k, 1, n, g[i][j]);
kok[i] = k;
}
}
int can(int m, int k[]) {
sort(k, k + m);
stack < pair < ii , int > > s;
s.push(mp(mp(inf, 0), 0));
for(int i = 0; i < m; i++){
int x = k[i], ara = k[i], alt = k[i], gel, fl = 0;
while(!s.empty() and s.top().st.st < x){
s.pop();
// cout << "Cikti" << endl;
}
while((int)s.size() > 1){
gel = s.top().nd;
int ne = qu(kok[gel], kok[x], 1, n, alt, s.top().st.st);
// cout << ne << " -> ";
if(ne <= ara)
ara -= ne;
else
break;
if(s.top().st.nd >= ara){
s.top().st.nd -= ara;
s.top().nd = x;
fl = 1;
break;
}
ara -= s.top().st.nd;
alt = s.top().st.st + 1;
s.pop();
// cout << "Cikti 2 " << ara << endl;
}
if(fl)
continue;
gel = s.top().nd;
ii y = bs(kok[gel], kok[x], 1, n, ara + qu(kok[gel], kok[x], 1, n, 1, alt - 1));
// cout << x << " " << gel << " " << s.top().st.st << " " << y.st << " " << y.nd << endl;
if(y.nd < 0)
return 0;
if(y.st == s.top().st.st){
s.top().st.nd += y.nd;
s.top().nd = x;
} else{
s.push(mp(y, x));
// cout << "geldi " << s.top().st.st << " " << s.top().st.nd << " " << s.top().nd << endl;
}
}
return 1;
}
