#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,minval,lazy;
} st[400009 * LOG];
int stnode;
void createchild(int id) {
if (st[id].leftchild) return;
st[id].leftchild = ++stnode;
st[id].rightchild = ++stnode;
}
void push_down(int id) {
if (st[id].lazy == 0) return;
st[st[id].leftchild].minval += st[id].lazy;
st[st[id].rightchild].minval += st[id].lazy;
st[st[id].leftchild].lazy += st[id].lazy;
st[st[id].rightchild].lazy += st[id].lazy;
st[id].lazy = 0;
}
void refine(int id) {
st[id].minval = min(st[st[id].leftchild].minval,st[st[id].rightchild].minval);
st[id].sum = st[st[id].leftchild].sum + st[st[id].rightchild].sum;
}
ll getsum(int id,ll l,ll r,int u,int v) {
if (l > v || r < u || st[id].sum == 0) return 0;
if (l >= u && r <= v) return st[id].sum;
ll mid = (l + r) >> 1;
createchild(id);
push_down(id);
return getsum(st[id].leftchild,l,mid,u,v) + getsum(st[id].rightchild,mid + 1,r,u,v);
}
void change(int id,ll l,ll r,ll pos,int type) {
if (l == r) {
if (type == -1) {
st[id].sum -= pos;
if (st[id].sum == 0) st[id].minval = 0;
} else {
if (st[id].sum == 0) st[id].minval = getsum(1,1,lim,1,pos - 1) + 1 - pos;
st[id].sum += pos;
}
return;
}
ll mid = (l + r) >> 1;
createchild(id);
push_down(id);
if (pos <= mid) change(st[id].leftchild,l,mid,pos,type);
else change(st[id].rightchild,mid + 1,r,pos,type);
refine(id);
}
void update(int id,ll l,ll r,ll u,ll v,ll val) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
st[id].minval += val;
st[id].lazy += val;
return;
}
ll mid = (l + r) >> 1;
createchild(id);
push_down(id);
update(st[id].leftchild,l,mid,u,v,val);
update(st[id].rightchild,mid + 1,r,u,v,val);
refine(id);
}
} SegTree;
bool init(int cnt,ll maxsize,ll tmp[]) {
SegTree.stnode = 1;
lim = maxsize + 3;
for (int i = 0;i < cnt;i++) {
SegTree.change(1,1,lim,tmp[i],1);
SegTree.update(1,1,lim,tmp[i] + 1,lim,tmp[i]);
}
return SegTree.st[1].minval >= 0;
}
bool is_happy(int type,int cnt,ll tmp[]) {
for (int i = 0;i < cnt;i++) {
SegTree.change(1,1,lim,tmp[i],type);
SegTree.update(1,1,lim,tmp[i] + 1,lim,tmp[i] * type);
}
return SegTree.st[1].minval >= 0;
}
