#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define vt vector
#ifdef LOCAL
void print() {cerr << ']' << endl;}
template<typename Head, typename... Tail> void print(Head H, Tail... T) {cerr << ' ' << H; if(sizeof...(T)) cerr << ','; print(T...); }
template<typename T> ostream& operator << (ostream& os, vector<T> v){os << "["; bool first = 1; for(auto x : v) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator <<(ostream& os,pair<A, B> p) {return os << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename A, typename B, typename C> ostream& operator << (ostream& os, tuple<A, B, C> a) {os << '(' << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")"; return os;}
template<typename A, size_t S> ostream& operator << (ostream& os, array<A, S> a) {os << "["; bool first = 1; for(auto x : a) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A> ostream& operator << (ostream& os, set<A> s) {os << "["; bool first = 1; for(auto x : s) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator << (ostream& os, map<A, B> m) {os << "["; bool first = 1; for(auto x : m) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
#define dbg(...) cerr << '[' << #__VA_ARGS__ << ":", print(__VA_ARGS__);
#else
#define dbg(...)
#endif // LOCAL
const int INF = 1e9 + 5;
struct SegTree
{
vt<int> S;
int N;
SegTree(int _N)
{
N = 1;
while(N < _N) N *= 2;
S = vt<int>(2 * N, -INF);
}
void upd(int i, int x)
{
int u = i + N - 1;
S[u] = x;
for(u /= 2; u > 0; u /= 2) S[u] = max(S[2 * u], S[2 * u + 1]);
}
pair<int, int> findFirst(int x, int i)
{
if(i >= N) return make_pair(S[i], i - N + 1);
if(S[2 * i] >= x) return findFirst(x, 2 * i);
else return findFirst(x, 2 * i + 1);
}
};
const int mxN = 5e5 + 5;
vector<int> until[mxN];
int val[mxN];
int N;
SegTree s(1);
void init(int _N, int A[], int B[])
{
N = _N;
for(int i = 0; i < N; i++)
{
until[A[i]].push_back(B[i]);
}
for(int i = 0; i < mxN; i++) sort(until[i].begin(), until[i].end());
s = SegTree(N);
for(int i = 0, j = 1; i < mxN; i++)
{
for(int x : until[i])
{
s.upd(j, x);
val[j] = i;
j++;
}
}
}
int can(int M, int K[]) {
sort(K, K + M);
vt<pair<int, int>> changed;
bool ok = 1;
for(int i = 0; i < M && ok; i++)
{
int rem = K[i];
while(rem > 0)
{
auto cur = s.findFirst(K[i], 1);
if(cur.first == -INF || cur.second == -1 || val[cur.second] > K[i])
{
ok = 0;
break;
}
rem--;
assert(1 <= cur.second && cur.second <= N);
changed.push_back(make_pair(cur.second, cur.first));
s.upd(cur.second, -INF);
}
}
for(auto [a, b] : changed) s.upd(a, b);
return ok;
}
/*
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _N;
cin >> _N;
int A[_N], B[_N];
for(int i = 0; i < _N; i++) cin >> A[i] >> B[i];
init(_N, A, B);
int Q;
cin >> Q;
for(int _i = 0; _i < Q; _i++)
{
int M;
cin >> M;
int sizes[M];
for(int i = 0; i < M; i++) cin >> sizes[i];
cout << can(M, sizes) << "\n";
}
}
*/
/*
4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1
*/
