#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
typedef long long ll;
ll sz = 1, n;
struct Node {
Node *l, *r;
ll mn, lazy;
Node(ll a, ll b) : l(nullptr), r(nullptr), mn(-min(b - 1, n - 1)), lazy(0) {}
void apply(ll v) {
mn += v;
lazy += v;
}
void push(ll a, ll b) {
ll m = (a + b) / 2;
if (l == nullptr) l = new Node(a, m);
if (r == nullptr) r = new Node(m, b);
l->apply(lazy);
r->apply(lazy);
lazy = 0;
}
};
Node* root;
map<ll, int> co;
void ch(Node* here, ll l, ll r, ll a, ll b, ll v) {
if (r <= a || l >= b) return;
if (a <= l && r <= b) {
here->apply(v);
return;
}
here->push(l, r);
ll m = (l + r) / 2;
ch(here->l, l, m, a, b, v);
ch(here->r, m, r, a, b, v);
here->mn = min(here->l->mn, here->r->mn);
}
void ch(ll a, ll b, ll v) {
ch(root, 0, sz, a, b, v);
}
ll mn(Node* here, ll l, ll r, ll a, ll b) {
if (r <= a || l >= b) return INT64_MAX;
if (a <= l && r <= b) return here->mn;
here->push(l, r);
ll m = (l + r) / 2;
return min(mn(here->l, l, m, a, b), mn(here->r, m, r, a, b));
}
bool good() {
if (co.empty()) return true;
return mn(root, 0, sz, 1, co.rbegin()->first + 1) >= 0;
}
void add(ll v) {
++co[v];
ch(v + 1, n, v);
}
void rem(ll v) {
if (--co[v] == 0) co.erase(v);
ch(v + 1, n, -v);
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
n = maxCoinSize + 1;
while (sz < n) sz *= 2;
root = new Node(0, n);
ch(1, n, 1);
for (int i = 0; i < coinsCount; ++i) add(coins[i]);
return good();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
for (int i = 0; i < coinsCount; ++i) {
if (event == 1) add(coins[i]);
else rem(coins[i]);
}
return good();
}
