// ~ Be Name Khoda ~ //
#include "teams.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnl = 2e7 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const int lg = 21;
const ll inf = 1e18;
int n, newnode = 2, k[maxn5], m, root[maxn5];
vector <int> av[maxn5];
namespace seg{
int sum[maxnl], chil[maxnl][2];
void cop(int i, int j){
sum[i] = sum[j];
chil[i][0] = chil[j][0];
chil[i][1] = chil[j][1];
}
void add(int l, int r, int id, int v){
sum[v]++;
if(r - l == 1)
return;
int mid = (l + r) >> 1, v2 = newnode++;
if(id < mid){
cop(v2, chil[v][0]);
chil[v][0] = v2;
add(l, mid, id, v2);
}
else{
cop(v2, chil[v][1]);
chil[v][1] = v2;
add(mid, r, id, v2);
}
}
int get_first(int l, int r, int v1, int v2, int k){
//cout << "ya get first " << l << ' ' << r << ' ' << v1 << ' ' << v2 << ' ' << k << ' ' << sum[v1] << ' ' << sum[v2] << endl;
if(r - l == 1)
return l;
int mid = (l + r) >> 1;
if(sum[chil[v2][0]] - sum[chil[v1][0]] >= k)
return get_first(l, mid, chil[v1][0], chil[v2][0], k);
k -= sum[chil[v2][0]] - sum[chil[v1][0]];
return get_first(mid, r, chil[v1][1], chil[v2][1], k);
}
int get_sum(int l, int r, int lq, int rq, int v){
if(rq <= l || r <= lq || v == 0)
return 0;
////cout << "while getting sum " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << sum[v] << endl;
if(lq <= l && r <= rq)
return sum[v];
int mid = (l + r) >> 1;
return get_sum(l, mid, lq, rq, chil[v][0]) + get_sum(mid, r, lq, rq, chil[v][1]);
}
int get(int l1, int r1, int l2, int r2){
r1--; l1--;
ll sum = get_sum(0, n, l2, r2, root[r1]);
////cout << "ok now " << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << ' ' << sum << ' ' << seg::sum[root[0]] << ' ' << root[0] << endl;
if(l1 >= 0)
sum -= get_sum(0, n, l2, r2, root[l1]);
return sum;
}
}
struct chtnode{
int nxt, pre, cons, id;
bool rem;
void clear(){
nxt = -1;
id = cons = 0;
rem = false;
}
} node[maxn5];
namespace cht{
int ind = 0, cur = 0, st;
vector <pair<int, int>> todo[maxn5];
void clear(){
node[0].clear();
st = 0;
ind = 1;
cur = 0;
for(int i = 0; i <= m; i++)
todo[i].clear();
}
int get_tim(int a, int b){
//cout << "hey " << a << ' ' << b << ' ' << node[a].id << ' ' << node[b].id << endl;
ll lim = node[a].cons - node[b].cons;
//cout << node[b].cons << endl;
a = node[a].id; b = node[b].id;
//////cout << a << ' ' << root[a] << endl;
int all = seg::sum[root[b]] - seg::sum[root[a]];
//cout << a << ' ' << b << ' ' << lim << ' ' << all << endl;
int ans = seg::get_first(0, n, root[a], root[b], all - lim);
int pt = upper_bound(k, k + m, ans) - k;
//cout << "for " << ans << ' ' << pt << endl;
return max(cur, pt);
}
int get_max(int id){
//cout << "*********** " << id << endl;
cur = id;
while(todo[id].size()){
int x = todo[id].back().fi, y = todo[id].back().se;
todo[id].pop_back();
//cout << "removing " << id << ' ' << x << ' ' << y << ' ' << node[x].nxt << endl;
if(!node[x].rem && !node[y].rem && node[x].nxt == y){
//cout << "ok " << ' ' << node[x].id << ' ' << node[y].id << endl;
node[y].rem = true;
int z = node[y].nxt;
node[x].nxt = z;
if(z == -1){
st = x;
continue;
}
int ti = get_tim(x, z);
todo[ti].pb({x, z});
}
}
cur++;
//cout << "here " << st << ' ' << node[st].cons << ' ' << node[st].id << endl;
return node[st].cons + k[id] - seg::get(node[st].id + 1, k[id] + 1, k[id], n);
}
void add(int id, int cons){
node[ind].clear();
node[ind].cons = cons;
node[ind].id = id;
int ti = get_tim(st, ind);
//cout << "we have " << ti << endl;
todo[ti].pb({st, ind});
node[st].nxt = ind;
st = ind;
ind++;
}
}
void init(int N, int A[], int B[]) {
seg::sum[0] = seg::chil[0][0] = seg::chil[0][1] = 0;
n = N;
for(int i = 0; i < n; i++)
av[A[i]].pb(B[i]);
n++;
int last = 1;
seg::sum[1] = seg::chil[1][0] = seg::chil[1][1] = 0;
for(int i = 0; i < n; i++){
root[i] = newnode++;
seg::cop(root[i], last);
last = root[i];
for(auto u : av[i]){
root[i] = newnode++;
seg::cop(root[i], last);
last = root[i];
seg::add(0, n, u, root[i]);
}
////cout << i << ' ' << newnode << ' ' << root[i] << ' ' << seg::chil[root[i]][0] << ' ' << seg::chil[root[i]][1] << endl;
}
}
int can(int M, int K[]) {
m = M;
for(int i = 0; i < m; i++)
k[i] = K[i];
sort(k, k + m);
cht::clear();
int ans = 0;
for(int i = 0; i < m; i++){
int dp = cht::get_max(i);
//cout << i << ' ' << k[i] << ' ' << dp << endl;
ans = max(ans, dp);
cht::add(k[i], dp);
}
return ans <= 0;
}
