#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
const int N = 2e5 + 5, Q = 1e5 + 5, INF = 1e18;
int q;
arr<int, Q> qry;
int n;
arr<int, N> hg;
arr<int, N> mn, mx;
void prp_cmp() {
mn[n + 1] = INF, mx[n + 1] = -INF;
for (int i = n; i >= 1; i--) {
mn[i] = min(mn[i + 1], hg[i]);
mx[i] = max(mx[i + 1], hg[i]);
}
}
int srch(int x) {
int lw = 1, hg = n;
while (lw < hg) {
int md = (lw + hg + 1) / 2;
if (mx[md] - mn[md] >= x) lw = md;
else hg = md - 1;
}
return (mx[lw] - mn[lw] >= x) ? lw : -1;
}
int slv(int x) {
int i = srch(x);
if (i == -1) return hg[n];
if (hg[i] == mn[i]) return x - (mx[i] - hg[n]);
else return (hg[n] - mn[i]);
}
vec<sig> distribute_candies(vec<sig> _qry, vec<sig> _l, vec<sig> _r, vec<sig> _x) {
q = _qry.size();
for (int i = 1; i <= q; i++) qry[i] = _qry[i - 1];
n = _x.size() + 2;
hg[1] = INF, hg[2] = 0;
for (int i = 3; i <= n; i++) hg[i] = hg[i - 1] + _x[i - 3];
prp_cmp();
vec<sig> ans;
for (int i = 1; i <= q; i++)
ans.push_back(slv(qry[i]));
return ans;
}
/*
for (int i = 1; i <= n; i++)
cout << hg[i] << " ";
cout << '\n';
*/
