Define an operation on $(i,i+1)$ as the act of decreasing both $h_i$ and $h_{i+1}$ by one. Also define $f$ to be the final hunger value.

Half Credit:

For inputs 1-8, it suffices to try all possible values of $f$ from $0$ to $\min(h_i)$ and see if they result in valid solutions. This can be done by sweeping left to right across $h$ and remedying instances where $h_i$ is greater than $f$ by doing operations on $(i,i+1)$ until one of $h_i$ or $h_{i+1}$ equals $f$. If there is a solution, this method must lead to it, because doing operations on $(i,i+1)$ is the only way to make $h_i$ equal $f$ assuming no more operations on $(i-1,i)$ are allowed.

This solution runs in $O(N\max(h_i))$ time.

Arpan's code:

#include<bits/stdc++.h>
#define int long long
#define nl "\n"
using namespace std;

int n;
const int inf = 1e18;

int cost(vector<int> h, int f){
	int o = 0;
	for (int i = 0; i < n - 1; i++){
		if (h[i] > f){
			int sub = min(h[i], h[i + 1]) - f;
			h[i] -= sub, h[i + 1] -= sub;
			o += sub * 2;
		}
	}
	for (int i = 0; i < n - 1; i++)
		if (h[i] != h[i + 1])
			return inf;
	return o;
}

int exe(){
	cin >> n; vector<int> h(n);
	int mn = inf, ans = inf;
	for (int& i : h) cin >> i, mn = min(mn, i);
	for (int f = 0; f <= mn; f++)
		ans = min(ans, cost(h, f));
	return (ans == inf ? -1 : ans);
}

signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios_base::failbit);
	int t; cin >> t;
	while (t--) cout << exe() << nl;
}

(Almost) Full Solution:

Consider any $i$ such that $h_{i-1} < h_{i}$. If $i=N$, then there is no solution because no operation can bring $h_N$ closer to $h_{N-1}$. Otherwise, the only way to make $h_i$ equal to $h_{i-1}$ is to do at least $h_i-h_{i-1}$ operations on $(i,i+1)$. Similar reasoning applies when $h_{i-1} > h_{i}$ (there is no solution if $i=2$, otherwise at least $h_{i-1}-h_i$ operations must be performed on $(i-2,i-1)$).

One approach is to repeatedly find the leftmost pair $(i-1,i)$ such that $h_{i-1}\neq h_{i}$ and perform the appropriate number of operations to make $h_{i-1}=h_{i}$. It can be proven that this terminates in $O(N^3)$ time, and is enough to solve all but the last input.

Ben's code:

#include <bits/stdc++.h>
using namespace std;
 
using i64 = int64_t;
 
i64 solve(vector<i64> h){
	const int N = (int)h.size();
	i64 ans = 0;
	auto operations = [&h,&ans](int idx, i64 num_op) {
		assert(num_op >= 0);
		h.at(idx) -= num_op; 
		h.at(idx+1) -= num_op;
		ans += 2*num_op;
	};
	bool flag = true;
	while (flag) {
		flag = false;
		for (int i = 1; i < N; ++i) if (h[i-1] != h[i]) {
			flag = true;
			if (h[i-1] < h[i]) {
				if (i == N-1) return -1;
				operations(i,h[i]-h[i-1]);
			} else {
				if (i == 1) return -1;
				operations(i-2,h[i-1]-h[i]);
			}
			break;
		}
	}
	// now h is all equal
	if (h[0] < 0) return -1;
	return ans;
}

int main() {
	int t; cin >> t;
	while (t--) {
		int N; cin >> N;
		vector<i64> H(N);
		for (auto& i: H) cin >> i;
		cout << solve(H) << "\n";
	}
}

Full Solution 1:

For a faster solution, let's start by moving left to right across $h$ and applying the necessary number of operations to $(i,i+1)$ to make $h_i$ equal to $h_{i-1}$ whenever we find $i$ such that $h_i > h_{i-1}$. After doing a pass through the array with this procedure, either $h_N > h_{N-1}$ (in which case there is no solution), or $h$ will be non-increasing ($h_i\le h_{i-1}$ for all $2\le i\le N$).

In the latter case, let's reverse $h$. Now $h$ will be non-decreasing ($h_i\ge h_{i-1}$ for all $2\le i\le N$). After one more pass with the above procedure, all elements of $h$ will be equal except possibly $h_N$. If $h_N > h_{N-1}$, then there is no solution. Otherwise, all elements of $h$ are equal, and it remains to verify whether these elements are non-negative.

This solution takes $O(N)$ time.

Arpan's code:

#include<bits/stdc++.h>
#define int long long
#define nl "\n"
using namespace std;

int exe(){
	int ans = 0, n;
	cin >> n; vector<int> h(n);
	for (int& i : h) cin >> i;
	if (n == 1) return 0;
	for (int j : {1, 2}){
		for (int i = 1; i < n - 1; i++){
			if (h[i] > h[i - 1]){
				int dif = h[i] - h[i - 1];
				ans += 2 * dif, h[i + 1] -= dif, h[i] = h[i - 1];
			}
		}
		if (h[n - 1] > h[n - 2]) return -1;
		// now h is non-increasing
		reverse(h.begin(), h.end());
		// now h is non-decreasing
	}
	// now h is all equal
	return h[0] < 0 ? -1 : ans;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios_base::failbit);
	int t; cin >> t;
	while (t--) cout << exe() << nl;
}

Full Solution 2:

Let $o_i$ be the total number of operations FJ performs on $(i,i+1)$ for each $1\le i<N$. The goal is to find the maximum $f$ such that there exists a solution to the following system of equations. Firstly, the final hunger value and the number of operations performed at every pair of indices must be non-negative:

Also,

The first solution in the analysis can be interpreted as trying all possible values of $f$ from $0$ to $\min(h_i)$, determining $o_1, o_2,\ldots, o_{N-1}$ in that order, and checking whether all of them are non-negative. For a faster solution, let’s rewrite the system of equations in the following form.

Observe that if $N$ is odd, the last equation uniquely determines $f$, so we can simply plug this value of $f$ into the brute force solution.

If $N$ is even, then if there exists some $f$ such that this system of equations, then $f’=0$ will as well. Let $o_1’, o_2’, \ldots, o_{N-1}’$ be the resulting numbers of operations. To find the maximum $f$, observe from the above equations that increasing $f’$ will decrease $o_1’, o_3’, \ldots, o_{N-1}’$, while $o_2’, o_4’, \ldots, o_{N-2}’$ remain constant. Thus, we may take $f=\min(o_1’,o_3’,\ldots,o_{N-1}’)$.

Ben's code:

#include <bits/stdc++.h>
using namespace std;
 
using i64 = int64_t;
 
i64 solve(const vector<i64>& H) {
	const int N = (int)H.size();
	i64 f = 0;
	for (int i = 0; i < N; ++i)
		f += (i%2 == 0 ? 1 : -1)*H[i];
	if (N%2 == 0) {
		if (f != 0) return -1;
	} else {
		if (f < 0) return -1;
	}
	i64 last_o = 0;
	vector<i64> o(N-1);
	for (int i = 0; i+1 < N; ++i) {
		last_o = o[i] = H[i]-f-last_o;
		if (o[i] < 0) return -1;
	}
	if (N%2 == 0) {
		i64 mn = o[0];
		for (int i = 0; i < N; i += 2)
			mn = min(mn,o[i]);
		for (int i = 0; i < N; i += 2)
			o[i] -= mn;
	}
	i64 sum_o = 0;
	for (i64 i: o) sum_o += i;
	return 2*sum_o;
}
 
int main() {
	int t; cin >> t;
	while (t--) {
		int N; cin >> N;
		vector<i64> H(N);
		for (auto& i: H) cin >> i;
		cout << solve(H) << "\n";
	}
}