#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
using ll = long long;
const ll MAXV = 1000000000005LL;
const int MAXC = 10000000;
int idxx;
struct Segment{
int L, R;
ll val;
} seg[MAXC];
void upd(int node, ll l, ll r, ll x, ll val){
if(l == r){
seg[node].val += val;
return;
}
ll mid = (l+r)/2;
if(!seg[node].L) seg[node].L = ++idxx;
if(!seg[node].R) seg[node].R = ++idxx;
if(x <= mid) upd(seg[node].L, l, mid, x, val);
else upd(seg[node].R, mid+1, r, x, val);
seg[node].val = seg[seg[node].L].val + seg[seg[node].R].val;
}
ll query(int node, ll l, ll r, ll tl, ll tr){
if(tl > r || l > tr || node == 0) return 0;
if(tl <= l && r <= tr) return seg[node].val;
ll mid = (l+r)/2;
return query(seg[node].L, l, mid, tl, tr) + query(seg[node].R, mid+1, r, tl, tr);
}
bool check(){
int tr = 1;
ll svi = query(1, 1, MAXV, 1, MAXV);
svi = min(svi, MAXV);
while(tr < svi){
ll kolko = query(1, 1, MAXV, 1, tr);
if(kolko < tr) return 0;
tr = kolko + 1;
}
return 1;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
idxx = 1;
for(int i=0; i<coinsCount; i++){
upd(1, 1, MAXV, coins[i], coins[i]);
}
return check();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
for(int i=0; i<coinsCount; i++){
if(event == 1){
upd(1, 1, MAXV, coins[i], coins[i]);
}
else{
upd(1, 1, MAXV, coins[i], -coins[i]);
}
}
return check();
}
/*
5 100
4 8 1 2 16
2
-1 2 2 8
1 3 7 9 2
*/
