#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define iii pair<ii,int>
#define pb push_back
const int MAX = (int) 2e5;
int n;
int a[MAX + 5];
int q;
struct queries {
int l, r, v;
queries(int _l = 0, int _r = 0, int _v = 0) : l(_l), r(_r), v(_v) {}
} query[MAX + 5];
vector<int> ans;
namespace sub4 {
ll s[MAX + 5];
pair<ll, int> smax[MAX + 5], smin[MAX + 5];
ll dis[MAX + 5];
bool check() {
for(int i = 1; i <= q; ++i) if(query[i].l != 1 || query[i].r != n) return 0;
return 1;
}
void solve() {
for(int i = 1; i <= q; ++i) s[i] = s[i - 1] + query[i].v;
smax[q].fi = smin[q].fi = s[q];
smax[q].se = -q;
smin[q].se = q;
for(int i = q - 1; i >= 1; --i) smax[i] = max(smax[i + 1], {s[i], -i});
for(int i = q - 1; i >= 1; --i) smin[i] = min(smin[i + 1], {s[i], i});
for(int i = 1; i <= q; ++i) dis[i] = smax[i].fi - smin[i].fi;
dis[0] = LLONG_MAX;
for(int i = 1; i <= n; ++i) {
int lo = -1, hi = q;
while(hi - lo > 1) {
int mid = lo + hi >> 1;
if (dis[mid] <= a[i]) hi = mid;
else lo = mid;
}
int c;
int A = -smax[hi].se, B = smin[hi].se;
int E = min(A, B);
c = (query[E].v < 0) ? -1 : 1;
if(c == -1) ans.pb(s[q] - s[E]);
else ans.pb(a[i] + s[q] - s[E]);
}
}
}
vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v) {
n = c.size();
for(int i = 0; i < n; ++i) a[i + 1] = c[i];
l.insert(l.begin(), 0);
r.insert(r.begin(), n-1);
v.insert(v.begin(), -1e9);
l.insert(l.begin(), 0);
r.insert(r.begin(), n-1);
v.insert(v.begin(), 1e9);
q = l.size();
for(int i = 0; i < q; ++i) query[i + 1] = queries(l[i] + 1, r[i] + 1, v[i]);
if(sub4::check()) sub4::solve();
return ans;
}
