#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 12;

ll sum[maxn];
int a[maxn];
int n, m, k;

vector<long long> minimum_costs(vector<int> H, vector<int> l, vector<int> r) {
   n = (int)H.size(), m = (int)l.size();
   for(int i = 0; i < n; i++) {
      a[i] = H[i];
   }

   vector<ll> ans(m, 1e18);
   for(int i = 0; i < m; i++) {
      stack<int> s;
      s.push(l[i] - 1);
      for(int j = l[i]; j <= r[i]; j++) {
         sum[j] = sum[j - 1];
         while(s.size() > 1 && a[s.top()] < a[j]) {
            int x = s.top();
            s.pop();
            sum[j] -= (x - s.top()) * a[x];
         }
         sum[j] += a[j] * (j - s.top());
         s.push(j);
      }

      while(s.size()) {
         s.pop();
      }
      s.push(r[i] + 1);
      ll val = 0;
      for(int j = r[i]; j >= l[i]; j--) {
         while(s.size() > 1 && a[s.top()] < a[j]) {
            int x = s.top();
            s.pop();
            val -= (s.top() - x) * a[x];
         }
         val += a[j] * (s.top() - j);
         s.push(j);
         ans[i] = min(ans[i], val + sum[j] - a[j]);
         sum[j] = 0;
      }
   }
   return ans;
}