#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 = 100'007;
int tab[N], answer[N];
ll sum[N]; int dod[N];
int que[N];
vector<int> qb[N], qe[N];
int Calc(ll x, int q)
{
//cerr << "C: " << x << "\n";
int pos = q;
ll mi = I, ma = -I, mi1 = I, ma1 = -I;
for(int i = 1; i <= q; ++i)
{
sum[i] = sum[i - 1] + dod[i];
//cerr << sum[i] << " ";
}
//cerr << "\n";
for(int i = q; i >= 1; --i)
{
mi = min(mi, sum[i]);
ma = max(ma, sum[i]);
if(ma - mi > x)
break;
}
//cerr << mi << " " << ma << "\n";
for(int i = q; i >= 1; --i)
{
mi1 = min(mi1, sum[i]);
ma1 = max(ma1, sum[i]);
if(ma1 != ma && mi1 != mi)
pos = i - 1;
else
break;
}
//cerr << pos << " " << sum[pos] << "\n";
if(ma == ma1)
return x + (sum[q] - sum[pos]);
return (sum[q] - sum[pos]);
}
void DoA(int n, int q)
{
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j < (int)qb[i].size(); ++j)
dod[qb[i][j]] += que[qb[i][j]];
for(int j = 0; j < (int)qe[i].size(); ++j)
dod[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;
}
