#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using ll = long long;
const ll inf = 3e18;
vector<ll> smart20(vector<int> a, vector<int> L, vector<int> R) {
int n = (int) a.size();
int q = (int) L.size();
vector<ll> ans(q, inf);
int logn = __lg(n) + 1;
vector<vector<int>> st(logn);
vector<vector<ll>> sp(logn);
st[0] = a;
for (int i = 1; i < logn; ++i) {
st[i].resize(n - (1 << i) + 1);
for (int j = 0; j <= (n - (1 << i)); ++j) {
st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
auto get = [&](int l, int r) {
if (!(r > l && l >= 0 && r <= n)) {
assert(false);
}
int lg = __lg(r - l);
return max(st[lg][l], st[lg][r - (1 << lg)]);
};
int mx = *max_element(a.begin(), a.end());
vector<int> g[mx + 1];
vector pref(mx + 1, vector<ll>(n)), suf(mx + 1, vector<ll>(n));
for (int i = 0; i < n; ++i) {
g[a[i]].push_back(i);
}
for (int i = 0; i < n; ++i) {
auto FirstBigger = [&](int x) {
int l = -1, r = i;
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (get(mid, i + 1) > x) {
l = mid;
} else {
r = mid;
}
}
return l;
};
int j = FirstBigger(a[i]);
ll val = a[i] * (i - j) + (j == -1 ? 0 : pref[0][j]);
for (int x = 0; x <= a[i]; ++x) {
pref[x][i] = val;
}
for (int x = a[i] + 1; x <= mx; ++x) {
j = FirstBigger(x);
pref[x][i] = x * (i - j) + (j == -1 ? 0 : pref[0][j]);
}
}
for (int i = n - 1; i > -1; --i) {
auto FirstBigger = [&](int x) {
int l = i, r = n + 1;
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (get(i, mid) > x) {
r = mid;
} else {
l = mid;
}
}
return l;
};
int j = FirstBigger(a[i]);
ll val = a[i] * (j - i) + (j == n ? 0 : suf[0][j]);
for (int x = 0; x <= a[i]; ++x) {
suf[x][i] = val;
}
for (int x = a[i] + 1; x <= mx; ++x) {
j = FirstBigger(x);
suf[x][i] = x * (j - i) + (j == n ? 0 : suf[0][j]);
}
}
sp[0].resize(n);
for (int i = 0; i < n; ++i) {
sp[0][i] = pref[a[i]][i] + suf[a[i]][i] - a[i];
}
for (int i = 1; i < logn; ++i) {
sp[i].resize(n - (1 << i) + 1);
for (int j = 0; j <= (n - (1 << i)); ++j) {
sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
}
}
for (int t = 0; t < q; ++t) {
int l = L[t], r = R[t];
vector<int> nxt;
for (int x = 1; x <= mx; ++x) {
auto it = lower_bound(g[x].begin(), g[x].end(), l);
if (it != g[x].end() && *it <= r) {
nxt.push_back(*it);
it = upper_bound(g[x].begin(), g[x].end(), r);
nxt.push_back(*prev(it));
}
}
sort(nxt.begin(), nxt.end());
nxt.resize(unique(nxt.begin(), nxt.end()) - nxt.begin());
int m = (int) nxt.size();
auto get_min = [&](int l, int r) {
if (!(r > l && l >= 0 && r <= n)) {
return inf;
}
int lg = __lg(r - l);
return min(sp[lg][l], sp[lg][r - (1 << lg)]);
};
for (int id = 0; id < m; ++id) {
int i = nxt[id];
int right = id == m - 1 ? r + 1 : nxt[id + 1];
{
ans[t] = min(ans[t], (pref[a[i]][i] + suf[a[i]][i] - a[i]) - (l == 0 ? 0 : pref[get(l, i + 1)][l - 1]) -
(r == n - 1 ? 0 : suf[get(i, r + 1)][r + 1]));
}
if (right <= r) {
ans[t] = min(ans[t], get_min(i + 1, right) - (l == 0 ? 0 : pref[get(l, i + 1)][l - 1]) -
(r == n - 1 ? 0 : suf[get(i + 1, r + 1)][r + 1]));
}
}
}
return ans;
}
vector<ll> stupid(vector<int> a, vector<int> L, vector<int> R) {
int n = (int) a.size();
int q = (int) L.size();
vector<ll> ans(q, inf);
vector<ll> pref(n), suf(n);
for (int t = 0; t < q; ++t) {
int l = L[t], r = R[t];
vector<int> stk;
ll sum = 0;
for (int i = l; i <= r; ++i) {
while (!stk.empty() && a[stk.back()] <= a[i]) {
int j = stk.back();
stk.pop_back();
sum += (a[i] - a[j]) * (ll) (j - (stk.empty() ? l - 1 : stk.back()));
}
stk.push_back(i);
sum += a[i];
pref[i] = sum;
}
stk.clear();
sum = 0;
for (int i = r; i >= l; --i) {
while (!stk.empty() && a[stk.back()] <= a[i]) {
int j = stk.back();
stk.pop_back();
sum += (a[i] - a[j]) * (ll) ((stk.empty() ? r + 1 : stk.back()) - j);
}
stk.push_back(i);
sum += a[i];
suf[i] = sum;
}
ans[t] = inf;
for (int i = l; i <= r; ++i) {
ans[t] = min(ans[t], pref[i] + suf[i] - a[i]);
}
}
return ans;
}
vector<ll> minimum_costs(vector<int> a, vector<int> L, vector<int> R) {
if (*max_element(a.begin(), a.end()) <= 20) {
return smart20(a, L, R);
} else {
return stupid(a, L, R);
}
}
