#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
#define int long long
int N, Q;
vector<signed> H,L,R;
int ST[MAXN][20];
int lg(signed x) {return 31 - __builtin_clz(x);}
void buildST() {
for(int i = 0; i < N; i++)
ST[i][0] = i;
for(int j = 1; j < 20; j++)
for(int i = 0; i + (1<<j) <= N; i++) {
if(H[ST[i][j-1]] > H[ST[i+(1<<(j-1))][j-1]]) {
ST[i][j] = ST[i][j-1];
}
if(H[ST[i][j-1]] < H[ST[i+(1<<(j-1))][j-1]]) {
ST[i][j] = ST[i+(1<<(j-1))][j-1];
}
if(H[ST[i][j-1]] == H[ST[i+(1<<(j-1))][j-1]]) {
if(rand()%2)
ST[i][j] = ST[i][j-1];
else
ST[i][j] = ST[i+(1<<(j-1))][j-1];
}
}
}
int query(int l, int r) {
int dif = (r-l+1);
int j = lg(dif);
j++;
int i = l;
if(H[ST[i][j-1]] > H[ST[r+1-(1<<(j-1))][j-1]]) {
return ST[i][j-1];
}
if(H[ST[i][j-1]] < H[ST[r+1-(1<<(j-1))][j-1]]) {
return ST[r+1-(1<<(j-1))][j-1];
}
if(H[ST[i][j-1]] == H[ST[r+1-(1<<(j-1))][j-1]]) {
if(rand()%2)
return ST[i][j-1];
else
return ST[r+1-(1<<(j-1))][j-1];
}
return -1;
}
int solve(int l, int r) {
if(l>r) return 0;
int idx = query(l, r);
int res = (r-l+1)*H[idx];
res = min(res, (idx-l+1)*H[idx] + solve(idx+1, r));
res = min(res, (r-idx+1)*H[idx] + solve(l, idx-1));
return res;
}
vector<long long> minimum_costs(vector<signed> H_, vector<signed> L_,
vector<signed> R_) {
H=H_;L=L_;R=R_;
Q = L.size();
N = H.size();
srand(time(NULL));
buildST();
vector<long long> C(Q);
for(int i = 0; i < Q; i++) {
C[i] = solve(L[i], R[i]);
}
return C;
}
