#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 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 (l1+r1 - l2 - r2 <= v) return c->l;
if (c->l == c->r) return n+1;
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,m+1,c->r,0);
if (!c2->c[1]) c2->c[1] = new node(nullptr, nullptr, m+1,c->r,0);
return q2(c->c[1],c2->c[1],v);
} else {
if (!c->c[0]) c->c[0] = new node(nullptr,nullptr,c->l,m,0);
if (!c2->c[0]) c2->c[0] = new node(nullptr, nullptr,c->l,m,0);
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);
}
void init(int N, int A[], int B[]){
n = N;
for (int i = 0; i < mxN; i++) roots[i] = nullptr;
vector<pii> all(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++;
}
}
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());
int res = n+1;
vector<pii> all;
all.pb({0,0});
//cout << M << ": ";
//for (int i = 0; i < m; i++) cout << k[i] << " ";
//cout << '\n';
for (int i = 0; i < m; i++){
while (sz(all) > 1 && bet(all[sz(all)-2], all[sz(all)-1]) <= k[i]) all.pop_back();
int cur = all.back().s + query(roots[k[i]], k[i]) - query(roots[all.back().f], k[i]) - k[i];
// cout << k[i] << ',' << cur << " ";
pii temp = {k[i],cur};
res = min(res, cur);
while (sz(all) > 1 && bet(all[sz(all)-2], all[sz(all)-1]) <= bet(all[sz(all)-1], temp)) all.pop_back();
all.pb(temp);
}
// cout << '\n';
return (res>=0);
}
/*
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
// cout << N << '\n';
int A[N];
int B[N];
for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
init(N,A,B);
int q;
cin >> q;
// cout << q << '\n';
int m;
for (int i = 0; i < q; i++){
cin >> m;
int k[m];
for (int j = 0; j < m; j++) cin >> k[j];
// cout << m <<" ";
// for (int j = 0; j < m; j++) cout << k[j] << " ";
// cout << '\n';
cout << can(m,k) << "\n";
}
return 0;
}
*/
