#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int MAXVAL = 8e6;
ll M;
map<ll, int> MM;
struct Node
{
ll val, lazy, pl, pr;
int lc, rc;
Node() : val(0), lazy(0), lc(-1), rc(-1), pl(-1), pr(-1) {}
};
Node nodes[MAXVAL];
int ncnt;
int newNode()
{
return ncnt++;
}
void update(int node, ll tl, ll tr, ll l, ll r, ll k)
{
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
nodes[node].lazy+=k;
return;
}
ll mid=tl+tr>>1;
if(nodes[node].pl!=-1)
{
if(nodes[node].pl<=mid)
{
nodes[node].lc=newNode();
ll ql=nodes[node].pl, qr=min(mid, nodes[node].pr);
if(ql==tl && qr==mid)
{
nodes[nodes[node].lc].lazy=nodes[node].val;
}
else
{
nodes[nodes[node].lc].pl=ql;
nodes[nodes[node].lc].pr=qr;
nodes[nodes[node].lc].val=nodes[node].val;
}
}
if(mid+1<=nodes[node].pr)
{
nodes[node].rc=newNode();
ll ql=max(mid+1, nodes[node].pl), qr=nodes[node].pr;
if(ql==mid+1 && qr==tr)
{
nodes[nodes[node].rc].lazy=nodes[node].val;
}
else
{
nodes[nodes[node].rc].pl=ql;
nodes[nodes[node].rc].pr=qr;
nodes[nodes[node].rc].val=nodes[node].val;
}
}
nodes[node].pl=-1; nodes[node].pr=-1;
nodes[node].val=min(nodes[node].val, 0ll);
}
if(l<=mid)
{
if(nodes[node].lc==-1)
{
nodes[node].lc=newNode();
nodes[nodes[node].lc].pl=l;
nodes[nodes[node].lc].pr=min(mid, r);
nodes[nodes[node].lc].val=k;
}
else
{
update(nodes[node].lc, tl, mid, l, min(mid, r), k);
}
}
if(mid+1<=r)
{
if(nodes[node].rc==-1)
{
nodes[node].rc=newNode();
nodes[nodes[node].rc].pl=max(mid+1, l);
nodes[nodes[node].rc].pr=r;
nodes[nodes[node].rc].val=k;
}
else
{
update(nodes[node].rc, mid+1, tr, max(mid+1, l), r, k);
}
}
nodes[node].val=INF;
if(nodes[node].lc!=-1) nodes[node].val=min(nodes[node].val, nodes[nodes[node].lc].val+nodes[nodes[node].lc].lazy);
if(nodes[node].rc!=-1) nodes[node].val=min(nodes[node].val, nodes[nodes[node].rc].val+nodes[nodes[node].rc].lazy);
}
int root;
ll query()
{
return nodes[root].val+nodes[root].lazy;
}
void push(ll x)
{
update(root, 1, M, x+1, M, x);
MM[x]++;
if(MM[x]==1)
{
auto it=MM.find(x);
ll val=-x;
if(next(it)!=MM.end()) val+=next(it)->first;
update(root, 1, M, prev(it)->first+1, x, val);
}
}
void pop(ll x)
{
update(root, 1, M, x+1, M, -x);
MM[x]--;
if(MM[x]==0)
{
auto it=MM.find(x);
ll val=x;
if(next(it)!=MM.end()) val-=next(it)->first;
update(root, 1, M, prev(it)->first+1, x, val);
MM.erase(x);
}
}
bool init(int coinsCount, ll maxCoinSize, ll coins[])
{
M=maxCoinSize;
root=newNode();
MM[0];
for(int i=0; i<coinsCount; i++) push(coins[i]);
return query()>=-1;
}
bool is_happy(int event, int coinsCount, ll coins[])
{
if(event == -1) for(int i=0; i<coinsCount; i++) pop(coins[i]);
else for(int i=0; i<coinsCount; i++) push(coins[i]);
return query()>=-1;
}
