#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
const int MAX_N = 75e4 + 5;
const long long INF = 1e18 + 7;
int N, Q;
long long H[MAX_N];
pair <int, int> table[MAX_N][20];
int table2[MAX_N][20];
vector <int> graph[MAX_N];
pair <int, int> getMax(int l, int r) {
int j = log2(r - l + 1);
return max(table[l][j], table[r - (1<<j) + 1][j]);
}
int getMin(int l, int r) {
int j = log2(r - l + 1);
return min(table2[l][j], table2[r - (1<<j) + 1][j]);
}
int build_tree(int l, int r) {
if(l > r) {
return -1;
}
int u = getMax(l, r).second;
int L = build_tree(l, u - 1);
int R = build_tree(u + 1, r);
if(L != -1) {
graph[u].push_back(L);
}
if(R != -1) {
graph[u].push_back(R);
}
return u;
}
long long dfs(int u, int l, int r, long long total = 0) {
long long now = total + H[u] * (r - l + 1);
for(auto v : graph[u]) {
if(v < u) {
now = min(now, dfs(v, l, u - 1, total + H[u] * (r - u + 1)));
}
else {
now = min(now, dfs(v, u + 1, r, total + H[u] * (u - l + 1)));
}
}
return now;
}
vector <long long> minimum_costs(vector <int> h, vector <int> L, vector <int> R) {
N = h.size(), Q = L.size();
vector <long long> C;
for(int i = 1; i <= N; i++) {
H[i] = h[i - 1];
}
for(int i = 0; i < Q; i++) {
L[i]++, R[i]++;
}
if(N <= 5000 and Q <= 5000) {
for(int i = 1; i <= N; i++) {
table[i][0] = make_pair(H[i], i);
}
for(int j = 1; j < 20; j++) {
for(int i = 1; i + (1<<j) - 1 <= N; i++) {
table[i][j] = max(table[i][j - 1], table[i + (1<<(j - 1))][j - 1]);
}
}
for(int i = 0; i < Q; i++) {
for(int i = 1; i <= N; i++) {
graph[i].clear();
}
C.push_back(dfs(build_tree(L[i], R[i]), L[i], R[i]));
}
}
else {
for(int i = 1; i <= N; i++) {
table2[i][0] = H[i];
}
for(int j = 1; j < 20; j++) {
for(int i = 1; i + (1<<j) - 1 <= N; i++) {
table2[i][j] = min(table2[i][j - 1], table2[i + (1<<(j - 1))][j - 1]);
}
}
for(int i = 0; i < Q; i++) {
int l = L[i], r = R[i], pos1 = N + 2, pos2 = N + 1;
while(l <= r) {
int mid = (l + r) / 2;
if(getMin(L[i], mid) == 1) {
r = mid - 1;
pos1 = mid;
}
else {
l = mid + 1;
}
}
l = pos1, r = R[i];
while(l <= r) {
int mid = (l + r) / 2;
if(getMin(mid, R[i]) == 1) {
l = mid + 1;
pos2 = mid;
}
else {
r = mid - 1;
}
}
C.push_back((pos2 - pos1 + 1) + 2 * ((R[i] - L[i] + 1) - (pos2 - pos1 + 1)));
}
}
return C;
}
