#pragma GCC optimize("Ofast")
#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];
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];
else
return ST[r+1-(1<<(j-1))][j-1];
}
int sameLeft[MAXN];
int sameRight[MAXN];
long long solve(long long l, long long r) {
if(l>r) return 0;
long long idx = query(l, r);
long long res = (r-l+1)*H[idx];
long long midL = max((long long)sameLeft[idx], l);
long long midR = min((long long)sameRight[idx], r);
res = min(res, (midR-l+1)*H[idx] + solve(midR+1, r));
res = min(res, (r-midL+1)*H[idx] + solve(l, midL-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();
sameLeft[0] = 0;
for(int i = 1; i < N; i++) {
if(H[i-1] == H[i])
sameLeft[i] = sameLeft[i-1];
else
sameLeft[i] = i;
}
sameRight[N-1] = N-1;
for(int i = N-1-1; i >= 0; i--) {
if(H[i+1] == H[i])
sameRight[i] = sameRight[i+1];
else
sameRight[i] = i;
}
vector<long long> C(Q);
for(int i = 0; i < Q; i++) {
C[i] = solve(L[i], R[i]);
}
return C;
}
