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

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 12;

ll sum[maxn];
ll a[maxn], pref[maxn];
int nxtl[maxn][21], nxtr[maxn][21];
int lg[maxn];
int n, m, k;

struct sparse {
   int mx[20][maxn];

   sparse() {
      for(int i = 0; i <= n; i++) {
         for(int k = 0; k < 20; k++) {
            mx[k][i] = 0;
         }
      }
   }

   void build(vector<int> a) {
      for(int i = 1; i <= n; i++) {
         mx[0][i] = a[i - 1];
         if(i > 1) lg[i] = lg[i / 2] + 1;
      }
      for(int k = 1; k < 20; k++) {
         for(int i = 1; i + (1 << k) - 1 <= n; i++) {
            mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + (1 << (k - 1))]);
         }
      }
   }

   int get(int l, int r) {
      int k = lg[r - l + 1];
      return max(mx[k][l], mx[k][r - (1 << k) + 1]);
   }
} st[21], t;

int get(int l, int r) {
   int mx = t.get(l, r), ans = 0;
   int tl = l, tr = r;
   if(a[l] < mx) {
      tl = nxtr[l][mx];
      ans = max(ans, get(l, tl - 1) + (mx - t.get(l, tl - 1)) * (tl - l));
   }
   if(a[r] < mx) {
      tr = nxtl[r][mx];
      ans = max(ans, get(tr + 1, r) + (mx - t.get(tr + 1, r)) * (r - tr));
   }
   ans = max(ans, st[mx].get(tl, tr));
   return ans;
}

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 = 1; i <= n; i++) {
      a[i] = H[i - 1];
      pref[i] = pref[i - 1] + a[i];
   }

   for(int i = 1; i <= n; i++) {
      for(int x = 1; x <= 20; x++) {
         nxtl[i][x] = nxtl[i - 1][x];
      }
      nxtl[i][a[i]] = i;
   }
   for(int x = 0; x <= 20; x++) {
      nxtr[n + 1][x] = n + 1;
   }
   for(int i = n; i; i--) {
      for(int x = 1; x <= 20; x++) {
         nxtr[i][x] = nxtr[i + 1][x];
      }
      nxtr[i][a[i]] = i;
   }
   t.build(H);
   for(int i = 1; i <= n; i++) {
      for(int x = 19; x >= 1; x--) {
         nxtl[i][x] = max(nxtl[i][x + 1], nxtl[i][x]);
         nxtr[i][x] = min(nxtr[i][x + 1], nxtr[i][x]);
      }
   }
   for(int k = 1; k <= 20; k++) {
      vector<int> v;
      for(int i = 1; i <= n; i++) {
         int val = 0;
         for(int x = 1; x < k; x++) {
            val += (k - x) * (nxtl[i][x] - nxtl[i][x + 1]);
            val += (k - x) * (nxtr[i][x + 1] - nxtr[i][x]);
         }
         v.push_back(val - (k - a[i]));
      }
      st[k].build(v);
   }

   vector<ll> ans(m);
   for(int i = 0; i < m; i++) {
      L[i]++, R[i]++;
      ans[i] = t.get(L[i], R[i]) * (R[i] - L[i] + 1) - get(L[i], R[i]);
   }
   return ans;
}