#include "happiness.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
long long mx;
struct Node{
long long sum;
int l, r;
Node() : sum(0), l(0), r(0){}
};
Node tree[40*201000];
int cnt = 2;
void update(int node, long long pos, long long add, long long l, long long r){
if(l == r && l == pos){
tree[node].sum += add;
}
else{
long long mid = (l+ r) / 2;
if(pos <= mid){
if(tree[node].l == 0) tree[node].l = cnt++;
update(tree[node].l, pos, add, l, mid);
}
else{
if(tree[node].r == 0) tree[node].r = cnt++;
update(tree[node].r, pos, add, mid+1, r);
}
tree[node].sum = tree[tree[node].l].sum + tree[tree[node].r].sum;
}
}
long long query(int node, long long L, long long R, long long l, long long r){
if(r < L || l > R) return 0;
if(L <= l && r <= R) return tree[node].sum;
long long mid = (l + r) / 2;
if(tree[node].l == 0){
tree[node].l = cnt++;
}
if(tree[node].r == 0)
tree[node].r = cnt++;
if(L > mid) return query(tree[node].r, L, R, mid+1, r);
else if(R <= mid) return query(tree[node].l, L, R, l, mid);
else{
return query(tree[node].l, L, R, l, mid) + query(tree[node].r, L, R, mid+1, r);
}
}
bool check(){
long long coin = 1, tot = query(1, 1, mx, 1, 1e12);
while(coin <= mx){
long long sum = query(1, 1, coin,1,1e12);
if(sum + 1 > mx) return true;
if(tot == sum) return true;
if(query(1, coin+1, sum+1,1,1e12) == 0) return false;
coin = sum + 1;
}
return true;
}
bool init(int n, long long M, long long a[]){
ios_base::sync_with_stdio(false);
cin.tie(0);
mx = M;
tree[1].sum = 0;
for(int i = 0; i < n; i++)
update(1, a[i], a[i], 1, 1e12);
return check();
}
bool is_happy(int e, int n, long long a[]){
for(int i = 0; i < n; i++)
update(1, a[i], a[i]*e, 1, 1e12);
return check();
}
