//In the name of God
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
const ll maxn = 5e5 + 100;
const ll maxm = 3e7;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll cnt[maxm], lc[maxm], rc[maxm];
ll root[maxn], t;
vector<ll> g[maxn];
pll c[maxn];
ll d[maxn], ee[maxn];
ll n;
ll add(ll id, ll s, ll e, ll x){
if(x < s || e <= x) return id;
ll nd = t++;
if(e - s == 1){
cnt[nd]++;
return nd;
}
ll mid = (s + e) >> 1;
lc[nd] = add(lc[id], s, mid, x);
rc[nd] = add(rc[id], mid, e, x);
cnt[nd] = cnt[id] + 1;
return nd;
}
void init(int N, int A[], int B[]){
n = N;
root[0] = t++;
for(ll i = 0; i < n; i++){
g[A[i]].pb(i);
c[i] = Mp(B[i], i);
}
sort(c, c + N);
for(ll i = 0; i < n; i++){
d[c[i].S] = i;
}
for(ll i = 0; i <= n; i++){
ee[i] = lower_bound(c, c + n, Mp(i, -inf)) - c;
}
for(ll i = 1; i <= n; i++){
root[i] = root[i - 1];
for(ll j : g[i]){
root[i] = add(root[i], 0, n, d[j]);
}
}
}
ll get(ll id, ll nd, ll s, ll e, ll l, ll r){
if(r <= s || e <= l) return 0;
if(l <= s && e <= r) return cnt[id] - cnt[nd];
ll mid = (s + e) >> 1;
return get(lc[id], lc[nd], s, mid, l, r) + get(rc[id], rc[nd], mid, e, l, r);
}
ll find(ll id, ll nd, ll s, ll e, ll x){
if(cnt[id] - cnt[nd] < x) return e;
if(e - s == 1) return s;
ll mid = (s + e) >> 1;
if(cnt[lc[id]] - cnt[lc[nd]] >= x) return find(lc[id], lc[nd], s, mid, x);
x -= cnt[lc[id]] - cnt[lc[nd]];
return find(rc[id], rc[nd], mid, e, x);
}
ll st(ll id, ll nd, ll s, ll e, ll l, ll r){
if(r <= s || e <= l) return nd;
if(l <= s && e <= r) return id;
ll mid = (s + e) >> 1;
ll dd = t++;
lc[dd] = st(lc[id], lc[nd], s, mid, l, r);
rc[dd] = st(rc[id], rc[nd], mid, e, l, r);
cnt[dd] = cnt[lc[dd]] + cnt[rc[dd]];
return dd;
}
int can(int m, int k[]){
ll now = 0;
sort(k, k + m);
for(ll i = 0; i < m; i++){
ll x = find(root[k[i]], now, 0, n, k[i] + get(root[k[i]], now, 0, n, 0, ee[k[i]]));
if(x == n || c[x].F < k[i]) return 0;
now = st(root[k[i]], now, 0, n, 0, x + 1);
}
return 1;
}
/*int main(){
freopen("teams.in", "r", stdin);
ll N, q, a[100], b[100], m, k[100];
cin >> N;
for(ll i = 0; i < N; i++){
cin >> a[i] >> b[i];
}
init(N, a, b);
cin >> q;
for(ll i = 0; i < q; i++){
cin >> m;
for(ll j = 0; j < m; j++){
cin >> k[j];
}
cout << "# " << can(m, k) << "\n";
}
return 0;
}*/
