#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "teams.h"
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 100;
int n;
pii a[MAXN + 10]; // {mn, mx}
int ps[MAXN + 10][MAXN + 10];
int sum(int u, int d, int l, int r) {
d--; l--;
return ps[r][u] + ps[l][d] - ps[l][u] - ps[r][d];
}
pii find_pos(int u, int d, int l, int r, int &rem){
int hi = u, lo = d - 1;
while(hi - lo > 1) {
int mi = (hi + lo) / 2;
if(sum(mi, d, l, r) <= rem) lo = mi;
else hi = mi;
}
rem -= sum(lo, d, l, r);
int y = hi;
hi = r, lo = l - 1;
while(hi - lo > 1) {
int mi = (hi + lo) / 2;
if(sum(y, y, l, mi) <= rem) lo = mi;
else hi = mi;
}
rem -= sum(y, y, l, lo);
int x = hi;
return pii(x, y);
// For(y, d, u) For(x, l, r) {
// int s = sum(y, y, x, x);
// if(rem < s) return pii(x, y);
// rem -= s;
// }
// assert(false);
}
void init(int N, int A[], int B[]) {
n = N;
memset(ps, 0, sizeof(ps));
For(i, 1, n) {
a[i] = pii(A[i - 1], B[i - 1]);
ps[A[i - 1]][B[i - 1]]++;
}
For(i, 1, n) For(j, 1, n) {
ps[i][j] += ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1];
}
sort(a + 1, a + n + 1);
// Forr(y, n, 1) For(x, 1, n) cerr << sum(y, y, x, x) << " \n"[x == n];
}
struct Ayaya {
int l, u, d, minus;
};
int can(int M, int K[]) {
sort(K, K + M);
vector<Ayaya> stk;
stk.eb((Ayaya){ 1, n, 1, 0 });
// auto out = [&]() {
// for(auto &i:stk) {
// cerr << i.l << " " << i.u << "~" << i.d << " (-" << i.minus << ")\n";
// }
// };
bool fail = false;
For(iter, 0, M - 1) {
int x = K[iter];
while(sz(stk) && (stk.back().u < x || stk.back().l > x)) stk.pop_back();
if(stk.empty()) {
fail = true;
goto END;
}
if(stk.back().d < x) stk.back().d = x;
// out();
int rem = x;
while(rem > 0) {
if(stk.empty()) {
fail = true;
goto END;
}
Ayaya aya = stk.back();
stk.pop_back();
int su = sum(aya.u, aya.d, aya.l, x) - aya.minus;
if(su <= rem) {
// cerr << su << " " << rem << " take all\n";
rem -= su;
continue;
}
rem += aya.minus;
pii pos = find_pos(aya.u, aya.d, aya.l, x, rem);
if(pos.S < aya.u) stk.eb((Ayaya){ aya.l, aya.u, pos.S + 1, 0 });
stk.eb((Ayaya){ pos.F, pos.S, pos.S, rem });
rem = 0;
}
if(stk.empty()) stk.eb((Ayaya){ x + 1, n, 1, 0 });
else if(stk.back().d > 1) stk.eb((Ayaya){ x + 1, stk.back().d - 1, 1, 0 });
}
END:
// cerr << "--- end of test ---\n";
if(fail) return 0;
return 1;
}
