#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
struct node
{
int left, right;
int sum, lazy;
int l, r;
int maxi;
node() {
sum=0, left=-1, right=-1, maxi=0;
}
};
vector<node> st;
void update(int root, int left, int right, int qLeft, int qRight, int nValue)
{
if (left>qRight || right<qLeft) return;
if (left>=qLeft && right<=qRight) {
st[root].sum+=left*nValue;
if (st[root].sum!=0) st[root].maxi=left;
else st[root].maxi=0;
return;
}
int mid=(left+right)/2;
if (mid>=qLeft) {
if (st[root].left==-1) {
st[root].left = sz(st);
st.push_back(node());
st[ st[root].left ].l=left, st[ st[root].left ].r=mid;
}
update(st[root].left, left, mid, qLeft, qRight, nValue);
}
if (mid<qRight) {
if (st[root].right==-1) {
st[root].right = sz(st);
st.push_back(node());
st[ st[root].right ].l=mid+1, st[ st[root].right ].r=right;
}
update(st[root].right, mid+1, right, qLeft, qRight, nValue);
}
st[root].sum=0;
if (st[root].left!=-1) st[root].sum+=st[ st[root].left ].sum;
if (st[root].right!=-1) st[root].sum+=st[ st[root].right ].sum;
st[root].maxi=0;
if (st[root].right!=-1) {
st[root].maxi=max(0LL, st[ st[root].right ].maxi-(st[root].left!=-1?st[st[root].left].sum:0));
}
if (st[root].left!=-1){
st[root].maxi=max(st[ st[root].left ].maxi, st[root].maxi);
}
}
int mx;
bool init(signed n, long long mxx, long long coins[]) {
mx=mxx;
st.push_back(node());
st[0].l=1, st[0].r=mx+1;
for (int i=0; i<n; i++) update(0, 1, mx+1, coins[i], coins[i], 1);
return st[0].maxi<=1;
}
bool is_happy(signed event, signed n, long long coins[]) {
for (int i=0; i<n; i++) update(0, 1, mx+1, coins[i], coins[i], event);
return st[0].maxi<=1;
}
