#include "happiness.h"
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
long long m;
vector<long long> seg, lzy;
vector<int> e, d, cnt;
bool init(int coinsCount, long long maxCoinSize, long long coins[]);
bool is_happy(int event, int coinsCount, long long coins[]);
int create();
void update(int pos, long long ini, long long fim, long long p, long long q, long long val, bool tp);
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
m = maxCoinSize;
create();
create();
return is_happy(1, coinsCount, coins);
}
bool is_happy(int event, int coinsCount, long long coins[]) {
for(int i = 0; i < coinsCount; i++){
update(1, 1, m, coins[i], coins[i], (-event) * (coins[i] - 1), 1);
update(1, 1, m, coins[i] + 1, m, event * coins[i], 0);
}
return seg[1] + lzy[1] >= 0;
}
int create(){
seg.push_back(0);
lzy.push_back(0);
e.push_back(0);
d.push_back(0);
cnt.push_back(0);
return seg.size() - 1;
}
void update(int pos, long long ini, long long fim, long long p, long long q, long long val, bool tp){
if(ini > q || fim < p) return;
if(ini >= p && fim <= q){
if(tp){
if(val >= 0) cnt[pos]--;
if(cnt[pos] == 0) seg[pos] += val;
if(val < 0) cnt[pos]++;
}
else{
seg[pos] += val;
lzy[pos] += val;
}
return;
}
long long mid = (ini + fim) >> 1;
if(e[pos] == 0){
int aux = create();
e[pos] = aux;
}
if(d[pos] == 0){
int aux = create();
d[pos] = aux;
}
update(e[pos], ini, mid, p, q, val, tp);
update(d[pos], mid + 1, fim, p, q, val, tp);
seg[pos] = min(seg[e[pos]], seg[d[pos]]) + lzy[pos];
}
