/*************************************
* author: marvinthang *
* created: 27.06.2023 11:42:33 *
*************************************/
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define REPD(i, n) for (int i = (n); i--; )
#define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; )
#define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
#include "debug.h"
#else
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define DB(...) 23
#define db(...) 23
#define debug(...) 23
#endif
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b) { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b) { if (a < b) { a = b; return true; } return false; }
// end of template
const long long INF = 1e18;
struct Line {
long long a, b;
int len;
Line(long long a = 0, long long b = 0, int len = 0): a(a), b(b), len(len) {}
long long eval(int x) {
return a * x + b;
}
friend print_op(Line) {
return out << make_pair(u.a, u.b);
}
};
vector <long long> minimum_costs(std::vector<int> H, vector <int> L, vector <int> R) {
int N = H.size();
int Q = L.size();
stack <int> st;
vector <int> par(N, -1);
REP(i, N) {
while (!st.empty() && H[st.top()] <= H[i]) st.pop();
if (!st.empty()) par[i] = st.top();
st.push(i);
}
while (!st.empty()) st.pop();
REPD(i, N) {
while (!st.empty() && H[st.top()] < H[i]) st.pop();
if (!st.empty() && (par[i] == -1 || H[par[i]] > H[st.top()])) par[i] = st.top();
st.push(i);
}
int root = find(ALL(par), -1) - par.begin();
vector <vector <pair <int, int>>> max_val;
max_val.push_back(vector<pair <int, int>>(N));
REP(i, N) max_val[0][i] = make_pair(H[i], i);
for (int k = 1; MASK(k) <= N; ++k) {
vector <pair <int, int>> nxt;
REP(i, N - MASK(k) + 1) nxt.push_back(max(max_val.back()[i], max_val.back()[i + MASK(k - 1)]));
max_val.push_back(nxt);
}
auto get_max = [&] (int l, int r) {
int h = __lg(r - l + 1);
return max(max_val[h][l], max_val[h][r - MASK(h) + 1]);
};
vector <vector <int>> queriesAt(N);
vector <long long> res(Q);
REP(i, Q) {
int ma = get_max(L[i], R[i]).se;
res[i] = 1LL * (R[i] - L[i] + 1) * H[ma];
queriesAt[ma].push_back(i);
}
REP(fl, 2) {
vector <int> left_child(N, -1), right_child(N, -1);
REP(i, N) if (~par[i]) (i < par[i] ? left_child[par[i]] : right_child[par[i]]) = i;
map <int, Line> cost;
vector <long long> lazy(N);
vector <int> cnt(N);
function <void(int, int, int)> dfs = [&] (int u, int prv, int nxt) {
long long cost_left = 0;
int l = left_child[u];
if (~l) {
dfs(l, prv, u - 1);
lazy[u] = lazy[l];
Line x = prev(cost.lower_bound(u))->se;
cnt[u] = cnt[l];
cost_left = x.eval(x.len - 1) + lazy[l];
}
cost[u] = Line(0, cost_left + H[u] - lazy[u], 1);
++cnt[u];
Line f(H[u], cost_left + H[u] + H[u]);
int r = right_child[u];
if (~r) {
dfs(r, u + 1, nxt);
for (int i: queriesAt[u]) {
auto [x, l] = *prev(cost.upper_bound(R[i]));
minimize(res[i], l.eval(R[i] - x) + lazy[r] + 1LL * (u - L[i] + 1) * H[u]);
}
lazy[r] += 1LL * (u - prv + 1) * H[u];
for (auto it = cost.find(u + 1); it != cost.end() && it->fi <= nxt; ) {
int v = it->fi;
Line g = it->se;
long long x = f.eval(f.len + g.len - 1);
long long y = g.eval(g.len - 1) + lazy[r];
it = cost.erase(it);
--cnt[r];
if (x <= y) {
f.len += g.len;
} else {
int low = 0, high = g.len - 1;
while (low <= high) {
int m = low + high >> 1;
if (f.eval(f.len + m) > g.eval(m) + lazy[r]) high = m - 1;
else low = m + 1;
}
f.len += low;
cost[v + low] = Line(g.a, g.b + g.a * low, g.len - low);
++cnt[r];
break;
}
}
if (f.len) {
f.b -= lazy[u];
cost[u + 1] = f;
++cnt[u];
}
if (cnt[u] <= cnt[r]) {
for (auto it = cost.find(prv); it->fi <= u + f.len; ++it)
it->se.b += lazy[u] - lazy[r];
lazy[u] = lazy[r];
} else {
for (auto it = cost.find(u + f.len + 1); it != cost.end() && it->fi <= nxt; ++it)
it->se.b += lazy[r] - lazy[u];
}
cnt[u] += cnt[r];
}
};
dfs(root, 0, N - 1);
root = N - root - 1;
reverse(ALL(par));
reverse(ALL(queriesAt));
REP(i, N) if (~par[i]) par[i] = N - par[i] - 1;
reverse(ALL(H));
REP(i, Q) {
L[i] = N - L[i] - 1;
R[i] = N - R[i] - 1;
swap(L[i], R[i]);
}
}
return res;
}
#ifdef LOCAL
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "meetings.h"
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
file("meetings");
int N = read_int();
int Q = read_int();
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
H[i] = read_int();
}
std::vector<int> L(Q), R(Q);
for (int j = 0; j < Q; ++j) {
L[j] = read_int();
R[j] = read_int();
}
std::vector<long long> C = minimum_costs(H, L, R);
cout << "answer:\n";
for (size_t j = 0; j < C.size(); ++j) {
printf("%lld\n", C[j]);
}
return 0;
}
#endif
