#include <iostream>
#include <vector>
// #include "meetings.h"
using namespace std;
const int N = 1<<20;
int Mx[N][20];
long long pre[N], suf[N];
vector<long long> Ans;
vector<int> quer[N];
void solve(vector<int> &H, vector<int> &L, vector<int> &R, int l, int r){
if (r < l)
return;
int b = 31 - __builtin_clz(r - l + 1), m = Mx[r - (1<<b) + 1][b];
if (H[Mx[l][b]] >= H[m])
m = Mx[l][b];
// cout<<m<<endl;
solve(H, L, R, l, m - 1);
solve(H, L, R, m + 1, r);
for (int i : quer[m])
Ans[i] = min(suf[L[i]] + 1LL * (R[i] - m + 1) * H[m], pre[R[i]] + 1LL * (m - L[i] + 1) * H[m]);
pre[m] = (m > l ? pre[m - 1] : 0) + H[m];
for (int i=m+1;i<=r;i++)
pre[i] = min(pre[i] + 1LL * (m - l + 1) * H[m], pre[m] + 1LL * (i - m) * H[m]);
suf[m] = (r > m ? suf[m + 1] : 0) + H[m];
for (int i=m-1;i>=l;i--)
suf[i] = min(suf[i] + 1LL * (r - m + 1) * H[m], suf[m] + 1LL * (m - i) * H[m]);
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
int n = H.size(), q = L.size();
Ans.resize(q, 0);
for (int i=n-1;i>=0;i--){
Mx[i][0] = i;
for (int j=0;j<19;j++){
if (i + (1<<j) >= n or H[Mx[i+(1<<j)][j]] <= H[Mx[i][j]])
Mx[i][j+1] = Mx[i][j];
else
Mx[i][j+1] = Mx[i + (1<<j)][j];
}
}
for (int i=0;i<q;i++){
int b = 31 - __builtin_clz(R[i] - L[i] + 1), m = Mx[R[i] - (1<<b) + 1][b];
if (H[Mx[L[i]][b]] >= H[m])
m = Mx[L[i]][b];
quer[m].push_back(i);
}
solve(H, L, R, 0, n - 1);
return Ans;
}
