#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++)
int maxH[5003][5003];
LL dp[5003][5003];
int maxI[5003];
Vi h;
struct NodeInfo {
int maxHeight;
int sumLO[21], sumLI[21];
int sumRI[21], sumRO[21];
int GetMaxSum() {
assert(sumLI[20] == sumRI[20]);
return sumLI[20];
}
void initSingle(int h) {
maxHeight = h;
memset(sumLO, 0, sizeof(sumLO));
memset(sumLI, 0, sizeof(sumLI));
memset(sumRI, 0, sizeof(sumRI));
memset(sumRO, 0, sizeof(sumRO));
forR(i, 21) {
sumLO[i] = sumRO[i] = min(20 - h, 20 - i);
sumLI[i] = sumRI[i] = 20 - h;
}
}
void update(const NodeInfo& left, const NodeInfo& right) {
maxHeight = max(left.maxHeight, right.maxHeight);
// LO
int sumR = right.sumLO[left.maxHeight];
{
forR(i, 21) {
sumLO[i] = left.sumLO[i] + right.sumLO[max(i, left.maxHeight)];
}
}
// RO
int sumL = left.sumRO[right.maxHeight];
{
forR(i, 21) {
sumRO[i] = right.sumRO[i] + left.sumRO[max(i, right.maxHeight)];
}
}
int MIDH = 0;
forR(i, 21) {
MIDH = max({ MIDH, left.sumRI[i] + right.sumLO[i], left.sumRO[i] + right.sumLI[i] });
}
// LI
{
forR(i, 21) {
sumLI[i] = left.sumLI[i] + sumR;
}
for (int i = left.maxHeight; i < 21; i++) {
sumLI[i] = max(sumLI[i], MIDH);
}
}
// RI
{
forR(i, 21) {
sumRI[i] = right.sumRI[i] + sumL;
}
for (int i = right.maxHeight; i < 21; i++) {
sumRI[i] = max(sumRI[i], MIDH);
}
}
}
};
struct SegNode {
int l, r;
SegNode* left, * right;
NodeInfo info;
inline int len() {
return r - l + 1;
}
NodeInfo maxRange(int f, int t) { // [f, t]
if (t < l || r < f) return NodeInfo{ true, 0, 0, 0 };
if (f <= l && r <= t) return info;
auto infoL = left->maxRange(f, t);
auto infoR = right->maxRange(f, t);
NodeInfo info;
info.update(infoL, infoR);
return info;
}
SegNode(int l, int r) {
this->l = l; this->r = r;
if (l == r) {
info.initSingle(h[l]);
left = right = nullptr;
} else {
int mid = (l + r) / 2;
left = new SegNode(l, mid);
right = new SegNode(mid + 1, r);
info.update(left->info, right->info);
}
}
};
VL minimum_costs(Vi H, Vi L, Vi R) {
int n = H.size(), q = L.size();
h = H;
int mH = 0;
forR(i, n) { mH = max(mH, H[i]); }
VL ans;
if (mH == 2) {
SegNode* root = new SegNode(0, n - 1);
#ifdef TEST_LOCAL
// check
forR(i, n) for (int j = i; j < n; j++) {
maxH[i][j] = H[i];
for (int x = i + 1; x <= j; x++) {
maxH[i][j] = max(maxH[i][j], H[x]);
}
}
forR(i, n) for (int j = i; j < n; j++) {
auto info = root->maxRange(i, j);
int cnt = j - i + 1;
int Qij = cnt * 20 - info.GetMaxSum();
bool hasEq = false;
for (int x = i; x <= j; x++) {
LL cost = 0;
for (int a = i; a <= x; a++) cost += maxH[a][x];
for (int a = x + 1; a <= j; a++) cost += maxH[x][a];
assert(Qij <= cost);
if (Qij == cost) hasEq = true;
}
assert(hasEq);
}
#endif
forR(i, q) {
auto info = root->maxRange(L[i], R[i]);
int cnt = R[i] - L[i] + 1;
ans.push_back(cnt * 20 - info.GetMaxSum());
}
return ans;
}
if (n <= 5000) {
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 {
LL hMax = H[mi];
dp[i][j] = min(dp[i][mi - 1] + hMax * (j - mi + 1),
dp[mi + 1][j] + hMax * (mi - i + 1));
}
}
}
#ifdef TEST_LOCAL
// check
forR(i, n) for (int j = i; j < n; j++) {
maxH[i][j] = H[i];
for (int x = i + 1; x <= j; x++) {
maxH[i][j] = max(maxH[i][j], H[x]);
}
}
forR(i, n) for (int j = i; j < n; j++) {
bool hasEq = false;
for (int x = i; x <= j; x++) {
LL cost = 0;
for (int a = i; a <= x; a++) cost += maxH[a][x];
for (int a = x + 1; a <= j; a++) cost += maxH[x][a];
assert(dp[i][j] <= cost);
if (dp[i][j] == cost) hasEq = true;
}
assert(hasEq);
}
#endif
forR(i, q) {
ans.push_back(dp[L[i]][R[i]]);
}
return ans;
}
}
#ifdef TEST_LOCAL
int main() {
minimum_costs(Vi{ 1, 1, 2, 1, 3, 10, 18, 20, 1, 19, 2, 2, 1, 1, 1, 2, 2, 2, 1 }, Vi{ 0, 1 }, Vi{ 1,2 });
return 0;
}
#endif
