#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second
const ll INF = 1ll<<40ll;
const int MX = 5e5;
const int N = 1<<24;
const int MOD = 1e9+7;
int n;
ll seg[N], pl[N], pr[N];
int segcnt=1;
ll tot = 0;
// sparse seg
void createChildren(int p) {
if(pl[p]) return;
pl[p] = segcnt++;
pr[p] = segcnt++;
}
void addSeg(ll i, ll v, int p=0, ll l=0, ll r=INF-1) {
if(i < l || i > r) return;
if(l == r) {
seg[p] += v;
tot += v;
return;
}
ll m=(l+r)/2;
createChildren(p);
addSeg(i,v,pl[p],l,m);
addSeg(i,v,pr[p],m+1,r);
seg[p] = seg[pl[p]]+seg[pr[p]];
}
ll getSeg(ll i, ll j, int p=0, ll l=0, ll r=INF-1) {
if(j < l || i > r) return 0;
if(i <= l && j >= r) return seg[p];
ll m=(l+r)/2;
if(pl[p]==0) return 0;
ll a=getSeg(i,j,pl[p],l,m);
ll b=getSeg(i,j,pr[p],m+1,r);
return a+b;
}
// problem
bool getAns() {
ll cur = 1;
while(cur < tot) {
ll res = getSeg(0,cur);
if(res < cur)
return false;
cur = res+1;
}
return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
RE(i,coinsCount)
addSeg(coins[i],1ll*coins[i]);
return getAns();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
RE(i,coinsCount)
addSeg(coins[i],event*coins[i]);
return getAns();
}
