求

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 7.1e3 + 7, Inf = 1e9 + 7;

int T;

int n, A[MAXN], F[MAXN][MAXN];

deque <int> Qr, Ql[MAXN];

void clear(deque <int> &Q) { while (! Q.empty()) Q.pop_back(); }

int main () {
	ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	for (cin >> T; T; T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> A[i], clear(Ql[i]);
		for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) F[i][j] = Inf;
		for (int i = 1; i <= n; i ++) F[i][i] = 0;
		
		for (int l = n - 1; l >= 1; l --) {
			int pos = l;
			clear(Qr); Ql[l + 1].push_back(l), Qr.push_back(l);
			for (int r = l + 1; r <= n; r ++) {
				while (pos < r && F[l][pos] <= F[pos + 1][r]) pos ++;
				
				int sum = Inf;
				
				while (!Qr.empty() && Qr.front() < pos) Qr.pop_front();
				if (!Qr.empty()) sum = min(sum, F[l][Qr.front()] + A[Qr.front()]);
				while (!Ql[r].empty() && Ql[r].front() >= pos) Ql[r].pop_front();
				if (!Ql[r].empty()) sum = min(sum, F[Ql[r].front() + 1][r] + A[Ql[r].front()]);
				
				F[l][r] = sum;
				
				while (!Qr.empty() && F[l][Qr.back()] + A[Qr.back()] > F[l][r] + A[r]) Qr.pop_back();
				Qr.push_back(r);
				
				if (l > 1) while (!Ql[r].empty() && F[Ql[r].back() + 1][r] + A[Ql[r].back()] > F[l][r] + A[l - 1]) Ql[r].pop_back();
				if (l > 1) Ql[r].push_back(l - 1);
			}
		}
		cout << F[1][n] << '\n';
	}
	return 0;
}