#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
using ll = long long;
#define thuhien ""
#define re exit(0);
const int LOG = 40;
ll lim;
//s[i - 1] - a[i]
struct DynamicSegmentTree {
struct node {
int leftchild,rightchild;
ll sum;
} st[400009 * LOG];
int stnode = 1;
void createchild(int id) {
if (st[id].leftchild) return;
st[id].leftchild = ++stnode;
st[id].rightchild = ++stnode;
}
void update(int id,long long l,long long r,long long pos,long long val) {
if (l > pos || r < pos) return;
if (l == r) {
st[id].sum += val;
return;
}
long long mid = (l + r) >> 1;
createchild(id);
update(st[id].leftchild,l,mid,pos,val);
update(st[id].rightchild,mid+1,r,pos,val);
st[id].sum = st[st[id].leftchild].sum + st[st[id].rightchild].sum;
}
ll get(int id,long long l,long long r,long long u,long long v) {
if (l > v || r < u || st[id].sum == 0) return 0;
if (l >= u && r <= v) return st[id].sum;;
long long mid = (l + r) >> 1;
createchild(id);
return get(st[id].leftchild,l,mid,u,v) + get(st[id].rightchild,mid + 1,r,u,v);
}
} SegTree;
bool check() {
ll currsum = 0,allsum = SegTree.get(1,1,lim,1,lim);
while (currsum < allsum) {
ll nextsum = SegTree.get(1,1,lim,1,currsum + 1);
if (nextsum <= currsum) return 0;
currsum = nextsum;
}
return 1;
}
bool init(int cnt,ll maxsize,ll tmp[]) {
lim = maxsize + 3;
for (int i = 0;i < cnt;i++) {
SegTree.update(1,1,lim,tmp[i],tmp[i]);
}
return check();
}
bool is_happy(int type,int cnt,ll tmp[]) {
for (int i = 0;i < cnt;i++) {
SegTree.update(1,1,lim,tmp[i],tmp[i] * type);
}
return check();
}
