#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ll long long int
#define pii pair<int,int>
const int N = 1e5+100, M = 5010, K = 22;
int rmq[N][K], dp[N][K], pd[N][K], lp[N][K], rp[N][K], rmq2[N][K];
ll pref[M][M];
ll h[N];
int rmq3[21][N][18];
int get(int l, int r){
int k = __lg(r-l+1);
return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
int get3(int l, int r, int d){
int k = __lg(r-l+1);
return max(rmq3[d][l][k], rmq[d][r-(1<<k)+1][k]);
}
int get2(int l, int r){
int k = __lg(r-l+1);
int lx = rmq2[l][k];
int rx = rmq2[r-(1<<k)+1][k];
return h[lx] >= h[rx] ? lx : rx;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
int n = H.size();
int q = L.size();
for(int i = 0; i < n; ++i) rmq[i+1][0] = H[i];
for(int i = 1; i <= n; ++i){
h[i] = H[i-1];
}
for(int i = 0; i < n; ++i) rmq2[i+1][0] = i;
for(int j = 1; j < K; ++j){
for(int i = 1; i + (1<<j) <= n + 1; ++i){
rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
int lx = rmq2[i][j-1];
int rx = rmq2[i+(1<<(j-1))][j-1];
if(H[lx-1] >= H[rx-1]) rmq2[i][j] = lx;
else rmq2[i][j] = rx;
}
}
// for(int i = 1; i <= n; ++i){
// pref[i][0] = 0;
// for(int j = 1; j <= n; ++j) pref[i][j] = pref[i][j - 1] + (i <= j ? get(i, j) : get(j, i));
// }
for(int i = 0; i < q; ++i) L[i]++, R[i]++;
vector<ll> C;
// if(n <= 5000 && q <= 5000){
// for(int _ = 0; _ < q; ++_){
// ll ans = 1e18;
// for(int i = L[_]; i <= R[_]; ++i){
// ll cur = pref[i][R[_]] - pref[i][L[_] - 1];
// // for(int j = L[_]; j <= R[_]; ++j){
// // if(i<=j) cur += get(i, j);
// // else cur += get(j,i);
// // }
// ans=min(ans,cur);
// }
// C.pb(ans);
// }
// return C;
// }
for(int d = 1; d <= 20; ++d){
dp[0][d] = 0;
int j = 0, j2 = 0;
for(int i = 1; i <= n; ++i){
if(h[i] > d){
lp[i][d] = i + 1;
dp[i][d] = 0;
j2 = i;
j = i;
}else if(h[i] == d){
if(i == 1 || h[i-1] > d){
dp[i][d] = d;
}else{
dp[i][d] = min((lp[i-1][d]-j2)*d + d + dp[i-1][d-1], (i-j)*d + dp[j][d]); // takes it all
}
j = i;
lp[i][d] = i;
}else{
lp[i][d] = j;
dp[i][d] = min(j == 0 ? i * d : dp[j-1][d] + d*(i-j+1), dp[i][d-1] + dp[j][d]);
}
// cerr << dp[i][d] << ' ';
}
// cerr << '\n';
}
for(int d = 1; d <= 20; ++d){
pd[n + 1][d] = 0;
int j = n + 1, j2 = n+1;
for(int i = n; i >= 1; --i){
if(h[i] > d){
rp[i][d] = i - 1;
pd[i][d] = 0;
j2 = i;
j = i;
}else if(h[i] == d){
if(i == n || h[i + 1] > d){
pd[i][d] = d;
}else{
pd[i][d] = min((j2-rp[i+1][d])*d + d + pd[i+1][d-1], (j-i)*d + pd[j][d]);
}
rp[i][d] = i;
j = i;
}else{
rp[i][d] = j;
pd[i][d] = min(j == n+1 ? (n-i+1) * d : pd[j+1][d] + d*(j-i+1), pd[i][d-1] + pd[j][d]);
}
// cerr << pd[i][d] << ' ' << rp[i][d] << '\n';
}
// cerr << '\n';
}
for(int d = 1; d <= 20; ++d){
for(int j = 1; j <= n; ++j){
rmq3[d][j][0] = 1e9;
if(h[j] >= d) rmq3[d][j][0] = dp[j-1][d] - (j-1-lp[j-1][d]) * d;
}
for(int j = 1; j < 18; ++j){
for(int i = 1; i + (1<<j) <= n+1; ++i){
rmq3[d][i][j] = min(rmq3[d][i][j-1], rmq3[d][i+(1<<(j-1))][j-1]);
}
}
}
for(int j = 0; j < q; ++j){
int ans = 1e9;
int l = L[j], r = R[j];
int mx = get(l, r);
if(mx==1){
C.pb(r-l+1);
continue;
}
ans = min({mx * (r-l+1), pd[l][mx-1] + (r-rp[l][mx]+1) * mx, dp[r][mx-1] + (lp[r][mx]-l+1) * mx});
int cnt = 0;
int lpt = get2(l, r);
ans = min(ans, (r-l+1)*mx + get3(lpt + 1, r, mx));
// for(int i = l; i <= r; ++i){
// if(h[i] == mx){
// ++cnt;
// if(cnt > 1 && i > l){
// ans = min(ans, dp[i-1][mx-1] + (r-i+1 + lp[i-1][mx]-l+1)*mx);
// }
// }
// }
C.pb(ans);
}
return C;
}
