#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 A(int i, int l) {
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 B(int i, int r) {
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];
}
int L(int i, int j) {
int lower = -1, upper = j + 1;
while (upper - lower > 1) {
int l = (lower + upper) / 2;
if (A(i, l) >= A(j, l))
lower = l;
else
upper = l;
}
return lower;
}
int R(int i, int j) {
int lower = j - 1, upper = n;
while (upper - lower > 1) {
int r = (lower + upper) / 2;
if (B(i, r) >= B(j, r))
upper = r;
else
lower = r;
}
return upper;
}
int pp_[N], pp1[N], prank[N], qq_[N], qq1[N], qrank[N], ll_[N], rr_[N];
long long A_(int i, int l) {
return ll_[i] < l ? A(i, l) : A_(ll_[pp1[i]] >= l ? pp1[i] : pp_[i], l);
}
long long B_(int i, int r) {
return rr_[i] > r ? B(i, r) : B_(rr_[qq1[i]] <= r ? qq1[i] : qq_[i], r);
}
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);
cnt = 0, pp_[0] = ll_[0] = -1, pp1[0] = -1, prank[0] = -1, qu[cnt++] = 0;
for (i = 1; i < n; i++) {
while (cnt >= 2 && A(qu[cnt - 1], ll_[qu[cnt - 1]] + 1) > A(i, ll_[qu[cnt - 1]] + 1))
cnt--;
pp_[i] = qu[cnt - 1], ll_[i] = L(i, pp_[i]), qu[cnt++] = i;
if (pp1[pp_[i]] != -1 && prank[pp1[pp_[i]]] == prank[pp_[i]])
pp1[i] = pp1[pp1[pp_[i]]], prank[i] = prank[pp_[i]] + 1;
else
pp1[i] = pp_[i], prank[i] = 0;
}
cnt = 0, qq1[n - 1] = qq_[n - 1] = rr_[n - 1] = n, qq1[n - 1] = n, qrank[n - 1] = -1, qu[cnt++] = n - 1;
for (i = n - 2; i >= 0; i--) {
while (cnt >= 2 && B(qu[cnt - 1], rr_[qu[cnt - 1]] - 1) > B(i, rr_[qu[cnt - 1]] - 1))
cnt--;
qq_[i] = qu[cnt - 1], rr_[i] = R(i, qq_[i]), qu[cnt++] = i;
if (qq1[qq_[i]] != n && qrank[qq1[qq_[i]]] == qrank[qq_[i]])
qq1[i] = qq1[qq1[qq_[i]]], qrank[i] = qrank[qq_[i]] + 1;
else
qq1[i] = qq_[i], qrank[i] = 0;
}
for (h = 0; h < q; h++) {
int l = ll[h], r = rr[h], m = get(l, r);
ans[h] = (long long) aa[m] * (r - l + 1);
if (m > l)
ans[h] = min(ans[h], A_(m - 1, l) - ((qq[m] == n ? 0 : dq[qq[m]]) + (long long) aa[m] * (qq[m] - r - 1)));
if (m < r)
ans[h] = min(ans[h], B_(m + 1, r) - ((pp[m] == -1 ? 0 : dp[pp[m]]) + (long long) aa[m] * (l - pp[m] - 1)));
}
return ans;
}
