#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
lint LIM = 1e12 + 10;
struct node{
lint sum, lz;
int l, r;
node(): sum(0), lz(0), l(0), r(0) {}
};
vector<node>seg;
int create(){
seg.push_back(node());
return seg.size() - 1;
}
void push(int v, lint l, lint r){
}
void update(int v, lint l, lint r, lint a, lint b, lint val){
if(b < l || r < a) return;
push(v, l, r);
if(a <= l && r <= b){
seg[v].sum += val;
push(v, l, r);
return;
}
lint m = (l + r) >> 1;
if(!seg[v].l){
int aux = create();
seg[v].l = aux;
}
if(!seg[v].r){
int aux = create();
seg[v].r = aux;
}
update(seg[v].l, l, m, a, b, val);
update(seg[v].r, m+1, r, a, b, val);
push(seg[v].l, l, m);
push(seg[v].r, m+1, r);
seg[v].sum = seg[seg[v].l].sum + seg[seg[v].r].sum;
}
lint query(int v, lint l, lint r, lint a, lint b){
if(b < l || r < a) return 0;
if(v == 0) return 0;
push(v, l, r);
if(a <= l && r <= b){
return seg[v].sum;
}
lint m = (l + r) >> 1;
return query(seg[v].l, l, m, a, b) + query(seg[v].r, m+1, r, a, b);
}
bool check(){
lint cur = 0, sum = seg[1].sum;
while(cur < sum){
lint cnt = query(1, 1, LIM, 1, cur);
if(cnt < cur) return 0;
cur = cnt + 1;
}
return 1;
}
bool init(int coinsCount, lint maxCoinSize, lint coins[]) {
create();
create();
for(int i=0;i<coinsCount;i++){
update(1, 1, LIM, coins[i], coins[i], coins[i]);
}
return check();
}
bool is_happy(int event, int coinsCount, lint coins[]) {
for(int i=0;i<coinsCount;i++){
update(1, 1, LIM, coins[i], coins[i], coins[i] * event);
}
return check();
}
