#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#include "candies.h"
#define ll long long
vector<int> distribute_candies(vector<int> C, vector<int> l, vector<int> r, vector<int> v){
int n = v.size();
vector<ll> pref(n, v[0]);
vector<pair<ll, ll>> b(n, pair<ll, ll>()), s(n, pair<ll, ll>());
for(int i = 1; i<n; i++) pref[i] = pref[i-1] + v[i];
b[n-1] = {pref[n-1], n-1};
s[n-1] = {pref[n-1], n-1};
for(int i = n-2; i>=0; i--){
b[i] = max(b[i+1], {pref[i], i});
s[i] = min(s[i+1], {pref[i], i});
}
vector<int> ans;
for(auto c : C){
ll l = 0, r = n-1;
if(b[0].first - s[0].first < c){
ans.push_back(pref[n-1]);
continue;
}
while(l<r){
ll mid = (l+r+1)/2;
if(b[mid].first - s[mid].first >= (ll)c) l = mid;
else r = mid-1;
}
if(b[l].second > s[l].second) ans.push_back(c + (int)((ll)pref[n-1] - (ll)pref[b[l].second]));
else ans.push_back((ll)pref[n-1] - (ll)pref[s[l].second]);
}
return ans;
}
