#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
#define sz(x) (int) (x).size()
#define pb push_back
#include "teams.h"
const int mxN = 5e5+5;
int n;
using sn = struct node*;
struct node {
sn c[2] = {nullptr, nullptr};
int v,l,r;
node(sn c1, sn c2, int tv, int tl, int tr){
c[0] = c1;
c[1] = c2;
v = tv;
l = tl;
r = tr;
}
};
sn roots[mxN];
sn upd(sn c, int t, int v){
if (c->l > t || c->r < t) return c;
sn temp = new node(c->c[0],c->c[1],c->v,c->l,c->r);
temp->v++;
if (c->l == c->r) return temp;
int m = (c->l + c->r)/2;
if (m >= t){
if (temp->c[0] == nullptr) temp->c[0] = new node(nullptr,nullptr,0,c->l,m);
temp->c[0] = upd(temp->c[0],t,v);
} else {
if (temp->c[1] == nullptr) temp->c[1] = new node(nullptr,nullptr,0,m+1,c->r);
temp->c[1] = upd(temp->c[1], t,v);
}
return temp;
}
int query(sn c, int t){
if (c == nullptr) return 0;
if (c->r < t) return 0;
if (c->l >= t) return c->v;
return query(c->c[0],t) + query(c->c[1],t);
}
//int ccc = 10;
int q2(sn c, sn c2, int v){
int l1 = 0;
int l2 = 0;
int r1 = 0;
int r2 = 0;
if (c->c[0]) l1 = c->c[0]->v;
if (c->c[1]) r1 = c->c[1]->v;
if (c2->c[0]) l2 = c2->c[0]->v;
if (c2->c[1]) r2 = c2->c[1]->v;
if (c->v - c2->v <= v) return c->l;
if (c->l == c->r) return c->r+1;
/* if (ccc > 0 && c->r < 10){
cout << c->l << "," << c->r << " " << l1 << ',' << r1 << " " << l2 << ',' << r2 << '\n';
cout << v << '\n';
ccc--;
}*/
int m = (c->l + c->r)/2;
if (r1 - r2 >= v) {
//go right side
if (!c->c[1]) c->c[1] = new node(nullptr,nullptr,0,m+1,c->r);
if (!c2->c[1]) c2->c[1] = new node(nullptr, nullptr, 0,m+1,c->r);
return q2(c->c[1],c2->c[1],v);
} else {
if (!c->c[0]) c->c[0] = new node(nullptr,nullptr,0,c->l,m);
if (!c2->c[0]) c2->c[0] = new node(nullptr, nullptr,0,c->l,m);
return q2(c->c[0], c2->c[0], v-(r1-r2));
}
}
int bet(pii a, pii b){
if (a.f > b.f) swap(a,b);
// when a gets better than b
//a + q(b,i) <= b
//q(b,i) <= b-a
int diff = b.s- a.s;
return q2(roots[b.f],roots[a.f],diff);
}
vector<pii> all;
void init(int N, int A[], int B[]){
n = N;
for (int i = 0; i < mxN; i++) roots[i] = nullptr;
all.resize(n);
for (int i = 0; i < n; i++) all[i].f = A[i], all[i].s = B[i];
sort(all.begin(),all.end());
roots[0] = new node(nullptr,nullptr,0,0,n);
int idx = 0;
for (int i = 1; i <= n; i++){
roots[i] = roots[i-1];
while (idx < sz(all) && all[idx].f == i) roots[i] = upd(roots[i],all[idx].s,1), idx++;
}
// for (pii c : all) cout << c.f << "," << c.s << " ";
// cout << '\n';
// cout << query(roots[1],3) << '\n';
}
bool brute(int M, vector<int> &K){
multiset<pii> cop;
for (int i = 0; i < n; i++) cop.insert({all[i].s, all[i].f});
// for (pii c :cop) cout << c.f << "," << c.s <<"\n";
// for (int c : K) cout << c << " ";
// cout << '\n';
int cnt;
auto it = cop.begin();
for (int i =0 ; i < M; i++){
it = cop.begin();
cnt = 0;
while (it != cop.end() && cnt < K[i]){
if (it->f < K[i] || it->s > K[i]){ it++; continue;}
cnt++;
it++;
cop.erase(prev(it));
}
// cout << i << " " << cnt << '\n';
// if (cnt < K[i]) cout << "DOESNT WROK " << i << " " << K[i] << ' ' << cnt << '\n';
if (cnt < K[i]) return 0;
}
return 1;
}
bool gw = 1;
int can(int M, int K[]){
int m = M;
vector<int> k(m);
for (int i = 0; i < m; i++) k[i] = K[i];
sort(k.begin(),k.end());
// bool bres = brute(m,k);
//if (n <=1000) cout << bres << ' ';
int res = n+1;
vector<pii> act;
act.pb({0,0});
// cout << M << ": ";
//// for (int i = 0; i < m; i++) cout << k[i] << " ";
// cout << '\n';
// cout << bet({0,0}, {1,2}) << '\n';
// cout << bet({1,2}, {2,3}) << '\n';
for (int i = 0; i < m; i++){
// cout << sz(act) << "-";
while (sz(act) > 1 && bet(act[sz(act)-2], act[sz(act)-1]) <= k[i]) act.pop_back();
int cur = act.back().s + query(roots[k[i]], k[i]) - query(roots[act.back().f], k[i]) - k[i];
// cout << act.back().f << "-" << k[i] << ',' << cur << " " << query(roots[k[i]], k[i]) << " " << query(roots[act.back().f],k[i]) << " - ";
pii temp = {k[i],cur};
res = min(res, cur);
while (sz(act) > 1 && bet(act[sz(act)-2], act[sz(act)-1]) <= bet(act[sz(act)-1], temp)) act.pop_back();
act.pb(temp);
}
//cout << '\n';
// if ((res>=0) != bres) cout << "UHO\n", gw = 0;
return (res>=0);
}
