#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct SparseNode{
SparseNode *left = NULL, *right = NULL;
ll sum = 0;
bool lazy = false;
SparseNode() {};
} *root = new SparseNode;
void add(SparseNode *curr, ll curr_left, ll curr_right, ll query, ll val){
if (curr_left > query || curr_right < query) return;
curr->sum += val;
if (curr_left == curr_right) return;
ll m = (curr_left+curr_right)/2;
if (!curr->left) curr->left = new SparseNode;
if (!curr->right) curr->right = new SparseNode;
add(curr->left, curr_left, m, query, val);
add(curr->right, m+1, curr_right, query, val);
}
ll range(SparseNode *curr, ll curr_left, ll curr_right, ll left, ll right){
if (curr_left > right || curr_right < left) return 0;
if (curr_left >= left && right >= curr_right) return curr->sum;
ll m = (curr_left+curr_right)/2;
if (!curr->left) curr->left = new SparseNode;
if (!curr->right) curr->right = new SparseNode;
return range(curr->left, curr_left, m, left, right)+range(curr->right, m+1, curr_right, left, right);
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
ll l = 0, r = 1e12;
for (int i = 0; i < coinsCount; i++){
add(root, l, r, coins[i], coins[i]);
}
ll currSum = 0;
bool works = true;
while (works){
ll nextSum = range(root, l, r, 1, currSum+1);
if (nextSum == currSum){
works = false;
}
currSum = nextSum;
}
return currSum >= range(root, l, r, l, r);
}
bool is_happy(int event, int coinsCount, long long coins[]) {
ll l = 0, r = 1e12;
if (event == -1){
for (int i = 0; i < coinsCount; i++){
add(root, l, r, coins[i], -coins[i]);
}
}else{
for (int i = 0; i < coinsCount; i++){
add(root, l, r, coins[i], coins[i]);
}
}
ll currSum = 0;
bool works = true;
while (works){
ll nextSum = range(root, l, r, 1, currSum+1);
if (nextSum == currSum){
works = false;
}
currSum = nextSum;
}
return currSum >= range(root, l, r, l, r);
}
