#include "meetings.h"
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vl;
const int N = 750000, H = 19;
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
int aa[N], qu[N], pp[N], qq[N], n; long long dp[N], dq[N];
int ii[H + 1][N], hh[N + 1];
void build(int n) {
int h, i, j;
for (i = 0; i < n; i++)
ii[0][i] = i;
for (h = 1; h <= H; h++)
for (i = 0; i < n; i++)
ii[h][i] = ii[h - 1][(j = i + (1 << h - 1)) >= n || aa[ii[h - 1][i]] >= aa[ii[h - 1][j]] ? i : j];
for (i = 1, h = 0; i <= n; i++) {
while (1 << h + 1 <= i)
h++;
hh[i] = h;
}
}
int get(int l, int r) {
int h = hh[r - l + 1];
return ii[h][aa[ii[h][l]] >= aa[ii[h][r - (1 << h) + 1]] ? l : r - (1 << h) + 1];
}
long long L(int l, int i) {
int j = get(l, i);
return dp[i] - ((pp[j] == -1 ? 0 : dp[pp[j]]) + (long long) aa[j] * (l - pp[j] - 1)) + dq[i] - aa[i];
}
long long R(int r, int i) {
int j = get(i, r);
return dq[i] - ((qq[j] == n ? 0 : dq[qq[j]]) + (long long) aa[j] * (qq[j] - r - 1)) + dp[i] - aa[i];
}
vl minimum_costs(vi aa_, vi ll, vi rr) {
int q = ll.size(), h, i, cnt;
vl ans(q);
n = aa_.size();
cnt = 0;
for (i = 0; i < n; i++) {
aa[i] = aa_[i];
while (cnt && aa[qu[cnt - 1]] < aa[i])
qq[qu[--cnt]] = i;
pp[i] = cnt == 0 ? -1 : qu[cnt - 1];
qu[cnt++] = i;
}
while (cnt--)
qq[qu[cnt]] = n;
for (i = 0; i < n; i++)
dp[i] = (pp[i] == -1 ? 0 : dp[pp[i]]) + (long long) aa[i] * (i - pp[i]);
for (i = n - 1; i >= 0; i--)
dq[i] = (qq[i] == n ? 0 : dq[qq[i]]) + (long long) aa[i] * (qq[i] - i);
build(n);
for (h = 0; h < q; h++) {
int l = ll[h], r = rr[h], m = get(l, r);
long long x, y;
ans[h] = (long long) aa[m] * (r - l + 1);
x = ((qq[m] == n ? 0 : dq[qq[m]]) + (long long) aa[m] * (qq[m] - r - 1));
y = ((pp[m] == -1 ? 0 : dp[pp[m]]) + (long long) aa[m] * (l - pp[m] - 1));
for (i = l; i < m; i++)
ans[h] = min(ans[h], L(l, i) - x);
for (i = m + 1; i <= r; i++)
ans[h] = min(ans[h], R(r, i) - y);
}
return ans;
}
