#include <bits/stdc++.h>
#define MAX 5010
#define INF 1000000000000000000LL
using namespace std;
typedef long long int lli;
int N, Q;
lli v[MAX];
lli prefix[MAX];
lli suffix[MAX];
lli lastGreater[MAX];
lli firstGreater[MAX];
vector<lli> ans;
vector<long long int> minimum_costs(vector<int> H, vector<int> l, vector<int> r)
{
N = H.size(); Q = l.size();
for(int g = 1 ; g <= N ; g++)
v[ g ] = H[g - 1];
for(int h = 0 ; h < Q ; h++)
{
int L = l[h] + 1;
int R = r[h] + 1;
int oldL = v[ L - 1 ];
int oldR = v[ R + 1 ];
v[L - 1] = v[R + 1] = INF;
lastGreater[ L ] = L - 1;
firstGreater[ R ] = R + 1;
prefix[ L ] = v[ L ];
suffix[ R ] = v[ R ];
prefix[ L - 1 ] = 0;
suffix[ R + 1 ] = 0;
for(int g = L + 1 ; g <= R ; g++)
{
int cur = g - 1;
while(v[g] >= v[cur]) cur = lastGreater[ cur ];
lastGreater[ g ] = cur;
prefix[ g ] = prefix[ cur ] + (g - cur)*v[ g ];
//printf("g = %d %d\n",g,prefix[g]);
}
//printf("\n");
for(int g = R - 1 ; g >= L ; g--)
{
int cur = g + 1;
while(v[g] >= v[cur]) cur = firstGreater[ cur ];
firstGreater[ g ] = cur;
suffix[ g ] = suffix[ cur ] + (cur - g)*v[ g ];
//printf("g = %d %d\n",g,suffix[g]);
}
//printf("\n\n\n");
lli mnAns = INF;
for(int g = L ; g <= R ; g++)
mnAns = min(mnAns , prefix[g] + suffix[g] - v[g]);
v[ L - 1 ] = oldL;
v[ R + 1 ] = oldR;
ans.push_back( mnAns );
}
return ans;
}
/*int main()
{
int nn, qq;
scanf("%d %d",&nn,&qq);
vector<int> hh(nn);
vector<int> ll(qq), rr(qq);
for(int g = 0 ; g < nn ; g++)
scanf("%d",&hh[g]);
for(int g = 0 ; g < qq ; g++)
scanf("%d %d",&ll[g],&rr[g]);
vector<lli> aux = minimum_costs(hh , ll , rr);
for(int g = 0 ; g < qq ; g++)
printf("%lld\n",aux[g]);
}*/
