#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 2000'000'000'000'000'000LL;
const int II = 1'000'000'007;
const ll M = 1000'000'007LL;
const int N = 1<<18;
int tab[N], answer[N];
int que[N];
ll drz1[N * 2], drz2[N * 2], laz[2 * N], s = 0LL;
vector<int> qb[N], qe[N];
void Push(int v)
{
for(int ne = v * 2; ne <= v * 2 + 1; ++ne)
{
drz1[ne] += laz[v];
drz2[ne] += laz[v];
laz[ne] += laz[v];
}
laz[v] = 0LL;
}
void Add(int v, int p, int k, int pz, int kz, ll x)
{
if(p > kz || k < pz) return;
if(p >= pz && k <= kz)
{
drz1[v] += x; drz2[v] += x;
laz[v] += x;
return;
}
Add(v * 2, p, (p + k) / 2, pz, kz, x);
Add(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
drz1[v] = min(drz1[v * 2], drz1[v * 2 + 1]) + laz[v];
drz2[v] = max(drz2[v * 2], drz2[v * 2 + 1]) + laz[v];
}
void A(int pos, int x)
{
s += (ll)x;
Add(1, 0, N - 1, pos, N - 1, x);
}
int Calc(ll x, int q)
{
int v = 1;
ll mi = I, ma = -I, mi1;
while(v < N)
{
Push(v);
if(max(ma, drz2[v * 2 + 1]) - min(mi, drz1[v * 2 + 1]) <= x)
{
ma = max(ma, drz2[v * 2 + 1]);
mi = min(mi, drz1[v * 2 + 1]);
v = v * 2;
}else
v = v * 2 + 1;
}
mi1 = mi;
mi = min(mi, drz1[v]); ma = max(ma, drz2[v]);
if(mi == mi1)
return (s - mi);
else
return x + (s - ma);
}
void DoA(int n, int q)
{
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j < (int)qb[i].size(); ++j)
A(qb[i][j], que[qb[i][j]]);
for(int j = 0; j < (int)qe[i].size(); ++j)
A(qe[i][j], -que[qe[i][j]]);
answer[i] = Calc(tab[i], q);
}
}
vector<int> distribute_candies(vector<int> _c, vector<int> _l, vector<int> _r, vector<int> _v)
{
int n = _c.size(), q = _l.size();
for(int i = 1; i <= n; ++i)
tab[i] = _c[i - 1];
que[1] = 2 * II;
que[2] = -2 * II;
qb[1].pb(1); qb[1].pb(2);
for(int i = 3; i <= q + 2; ++i)
{
que[i] = _v[i - 3];
qb[_l[i - 3] + 1].pb(i);
qe[_r[i - 3] + 2].pb(i);
}
q += 2;
DoA(n, q);
vector<int> ans;
for(int i = 1; i <= n; ++i)
ans.pb(answer[i]);
return ans;
}
