#include<bits/stdc++.h>
#define MAXN 750007
using namespace std;
const long long inf=1e17;
struct query{
int l,r;
}qs[MAXN];
int n,q,h[MAXN];
vector<long long> ans;
int dp[MAXN][20],power[20],lg[MAXN];
int best(int x,int y){
if(h[x]>=h[y])return x;
return y;
}
void calcdp(){
power[0]=1;
for(int i=1;i<20;i++)power[i]=power[i-1]*2;
for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
for(int i=1;i<=n;i++)dp[i][0]=i;
for(int j=1;j<20;j++){
for(int i=1;i+power[j]-1<=n;i++){
dp[i][j]=best(dp[i][j-1],dp[i+power[j-1]][j-1]);
}
}
}
int getmax(int l,int r){
if(l>r)return 0;
return best( dp[l][lg[r-l+1]] , dp[r-power[lg[r-l+1]]+1][lg[r-l+1]] );
}
unordered_map<long long,long long> res;
long long id(long long l,long long r){
return l*1000000+r;
}
long long solve(int l,int r){
if(l>r)return 0;
if(res[id(l,r)]!=0)return res[id(l,r)];
long long s=inf,val=h[getmax(l,r)];
vector<int> pos={l-1};
int x=l;
while(true){
x=getmax(x,r);
if(h[x]!=val)break;
pos.push_back(x);
x++;
}
pos.push_back(r+1);
for(int i=1;i<pos.size();i++){
s=min(s, solve(pos[i-1]+1,pos[i]-1) + val*(r-l+1-(pos[i]-pos[i-1]-1)) );
}
res[id(l,r)]=s;
return s;
}
vector<long long> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
n=int(H.size());
q=int(L.size());
for(int i=1;i<=n;i++){
h[i]=H[i-1];
}
calcdp();
for(int i=1;i<=q;i++){
ans.push_back(solve(L[i-1]+1,R[i-1]+1));
}
return ans;
}
/*int main(){
ans=minimum_costs({2, 4, 3, 5}, {0, 1}, {2, 3});
for(long long s:ans)cout<<s<<" ";
return 0;
}*/
