#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
#define forR(i, n) for (int i = 0; i < (n); i++)
LL dp[5003][5003];
int maxI[5003];
VL minimum_costs(Vi H, Vi L, Vi R) {
int n = H.size(), q = L.size();
memset(dp, 0, sizeof(dp));
forR(i, n) {
dp[i][i] = H[i];
maxI[i] = i;
}
for (int d = 1; d < n; d++) {
for (int i = 0; i + d < n; i++) {
int j = i + d;
if (H[j] > H[maxI[i]]) maxI[i] = j;
int mi = maxI[i];
if (mi == i) {
dp[i][j] = H[i] + dp[i + 1][j];
} else if (mi == j) {
dp[i][j] = H[j] + dp[i][j - 1];
} else {
int hMax = H[mi];
dp[i][j] = min(dp[i][mi - 1] + hMax * (j - mi + 1),
dp[mi + 1][j] + hMax * (mi - i + 1));
}
}
}
VL ans;
forR(i, q) {
ans.push_back(dp[L[i]][R[i]]);
}
return ans;
}
#ifdef TEST_LOCAL
int main() {
minimum_costs(Vi{ 2,4,3,5 }, Vi{ 0, 1 }, Vi{ 2, 3 });
return 0;
}
#endif
