#ifndef LOCAL
#include "meetings.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define left defined_left
#define right defined_right
using ll = long long;
const int N = 750005;
int n, q, a[N], x[N], y[N];
vector<ll> ans;
vector<int> qr[N];
int sp[23][N];
inline int get_pos(int x, int y) {
return (a[x] > a[y] ? x : y);
}
inline int get_max(int l, int r) {
int k = __lg(r - l + 1);
return get_pos(sp[k][l], sp[k][r - (1 << k) + 1]);
}
static const ll INF = 1e18;
struct Line {
ll a, b;
Line() { a = 0; b = INF; }
Line(ll a, ll b): a(a), b(b) {}
inline ll operator() (ll x) const {
return a * x + b;
}
};
struct ExtendedLichaoTree {
// +(0, x) in range [x, y]
// insert(a, b) in range [x, y]
// query(x)
// similar to (update range, get point)
Line IT[N << 2];
ll lazy[N << 2];
ExtendedLichaoTree() = default;
void push(int id) {
ll &val = lazy[id];
if (val == 0) return;
IT[id << 1].b += val;
lazy[id << 1] += val;
IT[id << 1 | 1].b += val;
lazy[id << 1 | 1] += val;
val = 0;
}
void update(int x, int y, ll val, int id, int l, int r) {
if (l > y || r < x) return;
if (x <= l && r <= y) {
IT[id].b += val;
lazy[id] += val;
return;
}
int mid = (l + r) / 2;
update(x, y, val, id << 1, l, mid);
update(x, y, val, id << 1 | 1, mid + 1, r);
}
inline void update(int x, int y, ll val) {
// +(0, val) in range [x, y]
if (x <= y) update(x, y, val, 1, 1, n);
}
void insert(int x, int y, Line val, int id, int l, int r) {
if (l > y || r < x) return;
int mid = (l + r) / 2;
push(id); // must push before update current value
if (x <= l && r <= y) {
if (l == r) {
if (IT[id](l) > val(l)) swap(IT[id], val);
return;
}
if (IT[id].a > val.a) swap(IT[id], val);
if (IT[id](mid) > val(mid)) {
swap(IT[id], val);
insert(x, y, val, id << 1 | 1, mid + 1, r);
} else {
insert(x, y, val, id << 1, l, mid);
}
return;
}
insert(x, y, val, id << 1, l, mid);
insert(x, y, val, id << 1 | 1, mid + 1, r);
}
inline void insert(int x, int y, Line val) {
// insert(a, b) in range [x, y]
if (x <= y) insert(x, y, val, 1, 1, n);
}
ll query(int x, int id, int l, int r) {
if (l == r) return IT[id](x);
push(id);
int mid = (l + r) / 2;
if (x <= mid) return min(IT[id](x), query(x, id << 1, l, mid));
else return min(IT[id](x), query(x, id << 1 | 1, mid + 1, r));
}
inline ll query(int x) {
// query(x)
return query(x, 1, 1, n);
}
} left, right;
void solve(int l, int r) {
if (l > r) return;
int m = get_max(l, r);
solve(l, m - 1);
solve(m + 1, r);
left.insert(m, m, Line(0, 0));
right.insert(m, m, Line(0, 0));
for (int id: qr[m]) {
int x = ::x[id], y = ::y[id];
ll res = left.query(x) + 1LL * (y - m + 1) * a[m];
res = min(res, 1LL * (m - x + 1) * a[m] + right.query(y));
ans[id] = res;
}
left.update(l, m, 1LL * (r - m + 1) * a[m]);
left.insert(l, m, Line(-a[m], 1LL * a[m] * (m + 1) + (m < r ? left.query(m + 1) : 0)));
right.update(m, r, 1LL * (m - l + 1) * a[m]);
right.insert(m, r, Line(a[m], -1LL * a[m] * (m - 1) + (l < m ? right.query(m - 1) : 0)));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
n = H.size();
q = L.size();
ans.assign(q, 0);
for (int i = 1; i <= n; i++) {
a[i] = H[i - 1];
sp[0][i] = i;
}
for (int k = 1; (1 << k) <= n; k++) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
sp[k][i] = get_pos(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
}
}
for (int i = 0; i < q; i++) {
x[i] = L[i] + 1;
y[i] = R[i] + 1;
qr[get_max(x[i], y[i])].emplace_back(i);
}
solve(1, n);
return ans;
}
#ifdef LOCAL
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<int> H(n);
for (int &x: H) cin >> x;
vector<int> L(q), R(q);
for (int i = 0; i < q; i++) cin >> L[i] >> R[i];
vector<ll> ans = minimum_costs(H, L, R);
for (ll x: ans) cout << x << '\n';
return 0;
}
#endif
