#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = (int)2e5+10;
ll mx, segTree[mxN*40];
int L[mxN*40], R[mxN*40];
int IND = 1;
void upd(ll x, ll v, int p=1, ll l=1, ll r=mx){
if(l==r){ segTree[p]+=v; return; }
ll mid = (l+r)/2;
if(x<=mid){
if(!L[p]) L[p]=++IND;
upd(x,v,L[p],l,mid);
}
else{
if(!R[p]) R[p]=++IND;
upd(x,v,R[p],mid+1,r);
}
segTree[p]= segTree[L[p]]+segTree[R[p]];
}
ll query(ll i, ll j, int p=1, ll l=1, ll r=mx){
if(i>r or j<l or i>j or !p) return 0;
if(i<=l and r<=j) return segTree[p];
ll mid = (l+r)/2;
return query(i,j,L[p],l,mid)+query(i,j,R[p],mid+1,r);
}
bool chk(){
ll coin = 1, tot = query(1,mx);
while(coin<=mx){
ll sum = query(1,coin);
if(sum+1>mx) return true;
if(tot==sum) return true;
if(query(coin+1,sum+1)==0) return false;
coin = sum+1;
}
return true;
}
bool init(int n, ll M, ll a[]) {
mx = M;
for(int i = 0; i < n; i++) upd(a[i],a[i]);
return chk();
}
bool is_happy(int e, int n, ll a[]) {
for(int i = 0; i < n; i++) upd(a[i],a[i]*e);
return chk();
}
