#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e5 + 20;
int a[maxn];
ll L[maxn];
vector<long long> minimum_costs(vector<int> H, vector<int> l, vector<int> r)
{
int n = H.size();
for(int i = 0; i < n; i++)
a[i] = H[i];
int q = l.size();
vector<ll> res;
for(int j = 0; j < q; j++)
{
vector<int> tmp;
tmp.pb(l[j] - 1);
ll sum = 0 , mn = 1e18;
int sz = tmp.size();
for(int i = l[j]; i <= r[j]; i++)
{
sum += a[i];
while(sz > 1 && a[tmp[sz - 1]] <= a[i])
{
sum += 1LL * (a[i] - a[tmp[sz - 1]]) * (tmp[sz - 1] - tmp[sz - 2]);
tmp.pop_back();
sz--;
}
L[i] = sum;
sz++;
tmp.pb(i);
}
tmp.clear();
tmp.pb(r[j] + 1);
sum = 0;
sz = 1;
for(int i = r[j]; i >= l[j]; i--)
{
sum += a[i];
while(sz > 1 && a[tmp[sz - 1]] <= a[i])
{
sum += 1LL * (a[i] - a[tmp[sz - 1]]) * (tmp[sz - 2] - tmp[sz - 1]);
tmp.pop_back();
sz--;
}
mn = min(mn , sum + L[i] - a[i]);
L[i] = 0;
sz++;
tmp.pb(i);
}
res.pb(mn);
}
return res;
}
