#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
#define int long long
using pii = pair<int, int>;
#define read(a) for (auto &x : a) cin >> x
#define V vector
#define show(a) for (auto x : a) cout << x << " "; cout << endl;
const int ninf = numeric_limits<int>::max();
struct Node
{
int l, r, s;
Node *ln, *rn;
};
void fn(Node *n)
{
if (n == nullptr) return;
fn(n->ln);
fn(n->rn);
delete n;
}
void u(Node *n, int x, int ct)
{
auto &[l, r, s, ln, rn] = *n;
s += x * ct;
if (l == r) return;
int m = (l + r) / 2;
if (x <= m)
{
if (!ln) ln = new Node {l, m, 0, nullptr, nullptr};
u(ln, x, ct);
}
else
{
if (!rn) rn = new Node {m + 1, r, 0, nullptr, nullptr};
u(rn, x, ct);
}
}
void showtree(Node *n, int lev)
{
for (int i = 0; i < lev; i ++) cout << ' ';
if (!n)
{
printf("[null]\n");
return;
}
printf("[%lld, %lld], s=%lld\n", n->l, n->r, n->s);
showtree(n->ln, lev + 2);
showtree(n->rn, lev + 2);
}
int qu(Node *n, int ql, int qr)
{
if (!n) return 0;
auto &[l, r, s, ln, rn] = *n;
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return s;
return qu(ln, ql, qr) + qu(rn, ql, qr);
}
Node *st;
bool check()
{
int cur = 1, tot = st->s;
while (cur < tot)
{
int s = qu(st, 1, cur);
if (s < cur) return false;
cur = s + 1;
}
return true;
}
bool init(signed n, int m, int coins[])
{
st = new Node {1, m, 0, nullptr, nullptr};
for (int i = 0; i < n; i ++)
{
u(st, coins[i], 1);
}
// showtree(st, 0);
return check();
}
bool is_happy(signed ev, signed c, int coins[])
{
for (int i = 0; i < c; i ++)
{
u(st, coins[i], ev);
}
// showtree(st, 0);
return check();
}
// #define NMAX 200000
// #define QMAX 100000
// static signed N, Q;
// static long long M;
// static long long coins[NMAX], A[5];
// signed main()
// {
// signed i, d;
// long long max_code;
// scanf("%d%lld", &N, &M);
// for (i = 0; i < N; ++i) {
// scanf("%lld", &coins[i]);
// }
// if (init(N, M, coins))printf("1\n");
// else printf("0\n");
// scanf("%d", &Q);
// for (i = 0; i < Q; ++i) {
// signed ck, c;
// scanf("%d%d", &ck, &c);
// for (int j = 0; j < c; j++) {
// scanf("%lld", &A[j]);
// }
// if (is_happy(ck, c, A))printf("1\n");
// else printf("0\n");
// }
// return 0;
// }
