#include "meetings.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
int n, q;
vector<ll> vec;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
n = H.size();
q = L.size();
vec.resize(n + 1);
for(int i = 1; i <= n; i++) vec[i] = H[i - 1];
vector<ll> fans(q, 1e18);
for(int hey = 0; hey < q; hey++){
int l = L[hey] + 1, r = R[hey] + 1;
vector<ll> ans(n + 1), anss(n + 1);
vector<pair<pair<int, int>, ll>> st;
for(int i = l; i <= r; i++){
ans[i] = ans[i - 1] + vec[i];
int nowl = i;
while(!st.empty() && st.back().second < vec[i]){
ans[i] -= st.back().second * (st.back().first.second - st.back().first.first + 1);
ans[i] += vec[i] * (st.back().first.second - st.back().first.first + 1);
nowl = st.back().first.first;
st.pop_back();
}
st.push_back(make_pair(make_pair(nowl, i), vec[i]));
}
vector<pair<pair<int, int>, ll>>().swap(st);
for(int i = r; i >= l; i--){
if(i < r) anss[i] = anss[i + 1] + vec[i];
else anss[i] = vec[i];
int nowl = i;
while(!st.empty() && st.back().second < vec[i]){
anss[i] -= st.back().second * (st.back().first.second - st.back().first.first + 1);
anss[i] += vec[i] * (st.back().first.second - st.back().first.first + 1);
nowl = st.back().first.second;
st.pop_back();
}
st.push_back(make_pair(make_pair(i, nowl), vec[i]));
}
for(int i = l; i <= r; i++){
fans[hey] = min(fans[hey], ans[i] + anss[i] - vec[i]);
//cout << hey << " " << i << " " << ans[i] << ' ' << anss[i] << " " << vec[i] << "\n";
}
}
return fans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp meetings.cpp
