#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int)1e6 + 12;
int n;
vector<pair<int, int>> a;
struct node{
	node *l = 0, *r = 0;
	int sum = 0;
	node (int s) {
		sum = s;
	}
	node(){}
	node(node *L, node *R) {
		l = L;
		r = R;
		sum = L->sum + R->sum;
	}
};
using pnode = node *;

pnode build(int tl = 1, int tr = n) {
	if(tl == tr) {
		return new node();
	}
	int tm = (tl + tr) >> 1;
	return new node(build(tl, tm), build(tm + 1, tr));
}
pnode tr[N];
pnode upd(int pos, pnode v, int tl = 1, int tr = n) {
	if(tl == tr) {
		return new node(v->sum + 1);
	} else {
		int tm = (tl + tr) >> 1;
		if(pos <= tm) {
			return new node(upd(pos, v->l, tl, tm), v->r);
		} else {
			return new node(v->l, upd(pos, v-> r, tm + 1, tr));
		}
	}
}
int get(int l, int r, pnode v, int tl = 1, int tr = n) {
	if(l > r || tl > r || l > tr) return 0;
	if(tl >= l && tr <= r) {
		return v->sum; 
	} else {
		int tm = (tl + tr) >> 1;
		return get(l, r, v->l, tl, tm) + get(l, r, v->r, tm + 1, tr);
	}
}
int sf[N];
void init(int nn, int A[], int B[]) {
	n = nn;
	for(int i = 0; i < n; i++) {
		a.emplace_back(A[i], B[i]);
		sf[A[i]]++;
	}
	sort(a.begin(), a.end());
	tr[n] = build();
	for(int i = n - 1; i >= 0; i--) {
		tr[i] = upd(a[i].second, tr[i + 1]);
	}
	for(int i = n; i >= 1; i--) {
		sf[i] += sf[i + 1];
	}
}
int c(int i, int j) {
	int it = upper_bound(a.begin(), a.end(), make_pair(i, (int)1e9)) - a.begin();
	int ret1 = get(j, n, tr[it]) - sf[j + 1];
	return ret1;
}
int col[N];
vector<int> q;

vector<int> dp;
int calc(int j, int i) {
	return dp[j] + c(q[j], q[i]) - q[i] * col[q[i]];
}
int can(int M, int K[]) {
	q.clear();
	dp.assign(M + 1, 0);
	ll sum = 0;
	for(int i = 0; i < M; i++) {
		col[K[i]] = 0;
	}
	for(int i = 0; i < M; i++) {
		sum += K[i];
		col[K[i]]++;
	}
	if(sum > n) return 0;
	q.push_back(0);
	for(int i = 0; i < M; i++) {
		q.push_back(K[i]);
	}
	sort(q.begin(), q.end());
	q.resize(unique(q.begin(), q.end()) - q.begin());
	set<int> cur;
	cur.insert(0);
	set<pair<int, int>> tr;

	auto find = [&](int i, int j){
		assert(i < j);
		int l = j, r = (int)q.size();
		while(r - l > 1) {
			int mid = (l + r) >> 1;
			if(calc(j, mid) < calc(i, mid)) {
				l = mid;
			} else {
				r = mid;
			}
		}
		return l;
	};
	auto add = [&](int i) {
		auto it1 = (*cur.rbegin());
		int val = find(it1, i);
		tr.insert({val, i});
		cur.insert(i);
	};
	auto del = [&](int i) {
		if(!cur.count(i)) return;
		cur.erase(i);
		auto it = cur.upper_bound(i);
		auto it1 = cur.upper_bound(i);
		if(it != cur.end() && it1 != cur.begin()) {
			it1--;
			tr.insert({find(*it1, *it), *it});
		}
	};
	for(int i = 1; i < (int)q.size(); i++) {
		int j = (*cur.rbegin());
		// cerr << j << "x\n";
		dp[i] = dp[j] + c(q[j], q[i]) - q[i] * col[q[i]];
		add(i);
		while(!tr.empty() && (*tr.begin()).first <= i) {
			auto [x, y] = (*tr.begin());
			tr.erase({x,y});
			del(y);
		}
		if(dp[i] < 0) return 0;
	}
	return 1;
}