#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <tuple>
#define ctz __builtin_ctzll
#define clz __builtin_clzll
using ull = unsigned long long;
char bf[20000000], *bp = bf;
void inline rd(auto &x) {
for (x = 0; !isdigit(*bp); bp++);
for (; isdigit(*bp); bp++)
x = x * 10 + (*bp ^ 48);
}
const int N = 7.5e5, LG = 17;
int n, m, tp, a[N], l[N], r[N], mx[N], q[N], p[N], bl[N], br[N];
unsigned long long b[N], ms[N + 1], pr[N], sf[N + 1], st[LG][N / 64];
long long ans[N], c[N], f[N];
std::vector<int>rg[N + 1];
std::vector<std::tuple<int, int, int>>qr[N];
bool inline ck(int u) {
return ms[u >> 6] >> (u & 63) & 1;
}
void inline gf(int &u) {
while (p[u] != u)
u = p[u] = p[p[u]];
}
int tl(int u) {
if (!~u)
return -1;
if (auto x = ms[u >> 6] & -1ull >> (~u & 63))
return (u | 63)^clz(x);
if (!(u >>= 6))
return -1;
if (ms[--u])
return u << 6 | 63 ^ clz(ms[u]);
return gf(u), ~bl[u] ? bl[u] << 6 | 63 ^ clz(ms[bl[u]]) : -1;
}
int tr(int u) {
if (auto x = ms[u >> 6] & -1ull << (u & 63))
return u & ~63 | ctz(x);
if (ms[u = (u >> 6) + 1])
return u << 6 | ctz(ms[u]);
return gf(u), br[u] << 6 | ctz(ms[br[u]]);
}
void md(int u) {
if (ms[u >> 6] &= ~(1ull << (u & 63)))
return;
auto mg = [](int x, int y) {
if (gf(x), gf(y), br[x] - bl[x] <= br[y] - bl[y])
p[x] = y, bl[y] = bl[x];
else
p[y] = x, br[x] = br[y];
};
u >>= 6, p[u] = u, bl[u] = u - 1, br[u] = u + 1;
if (u && !ms[u - 1])
mg(u - 1, u);
if (u + 1<n >> 6 && !ms[u + 1])
mg(u, u + 1);
}
void sv() {
for (int i = 0, t; i < n; qr[i].clear(), rg[i].clear(), i++) {
for (c[i] = 1e18; ~tp && b[q[tp]] <= b[i]; tp--)
if (c[i] = std::min(c[i], (a[q[tp]] - a[i]) * (i - 1ll) + c[q[tp]]), ck(q[tp]))
md(q[tp]);
auto upd = [&](int x) {
int y = x;
while (~(y = tl(y - 1)) && 1ll * (a[x] - a[y]) * i + c[x] - c[y] <= 0)
md(y);
if (~y && a[x] != a[y])
rg[std::min((c[y] - c[x]) / (a[x] - a[y]) + 1, 1ll * n)].push_back(x);
};
c[i] = std::min(c[i], f[i] = ~tp ? f[q[tp]] + 1ll * q[tp] * a[q[tp]] - 1ll * a[i] * q[tp] : a[i]);
for (upd(q[++tp] = i); int x : rg[i])
if (ck(x))
upd(x);
for (auto[x, y, z] : qr[i])
if (y < i)
t = tr(y + 1),
ans[x] = std::min(ans[x], 1ll * a[t] * i - 1ll * z * a[y] + c[t] - f[y]);
}
}
int main() {
fread(bf, 1, sizeof bf, stdin), rd(n), rd(m);
for (int i = 0; i < n; i++)
rd(a[i]), b[i] = 1ull * a[i] << 32 | i, qr[i].reserve(50);
for (int i = 0; i < n; i++)
pr[i] = i & 63 ? std::max(pr[i - 1], b[i]) : b[i];
for (int i = n; i--; sf[i] = ~i & 63 ? std::max(sf[i + 1], b[i]) : b[i], ms[i] |= 1ull << (i & 63))
for (ms[i] = ~i & 63 ? ms[i + 1] : 0; ms[i] && a[ctz(ms[i]) + (i & ~63)] < a[i];)
ms[i] -= ms[i] & -ms[i];
for (int i = 0; i<n >> 6; i++)
st[0][i] = sf[i << 6];
for (int i = 1, j; 1 << i <= n >> 6; i++)
for (j = 0; j + (1 << i) <= n >> 6; j++)
st[i][j] = std::max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
for (int i = 0, u, v, t; i < m; i++)
if (rd(l[i]), rd(r[i]), (u = l[i] + 64 >> 6) < (v = r[i] >> 6))
t = std::__lg(v - u), mx[i] = std::max({sf[l[i]], st[t][u], st[t][v - (1 << t)], pr[r[i]]});
else
mx[i] = u == v ? std::max(sf[l[i]], pr[r[i]]) : r[i] - clz(ms[l[i]] << (~r[i] & 63));
for (int i = 0; i < m; i++)
ans[i] = a[mx[i]] * (r[i] - l[i] + 1ll), qr[r[i]].push_back({i, mx[i], l[i] - 1});
memset(ms, -1, n + 8 >> 3), tp = -1, sv(), std::reverse(a, a + n), std::reverse(b, b + n);
for (int i = 0; i < m; i++)
qr[n - l[i] - 1].push_back({i, n - mx[i] - 1, n - r[i] - 2});
memset(ms, -1, n + 8 >> 3), tp = -1, sv();
for (int i = 0; i < m; i++)
std::cout << ans[i] << '\n';
}
