#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
#include <complex>
#include <numeric>
#include <assert.h>
#include <functional>
#include <climits>
#include <cstring>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using ll = long long;
using ld = long double;
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#ifndef LOCAL
#define endl "\n"
#endif
#define TT template <typename T>
mt19937 rnd(11);
TT
istream& operator>>(istream &in, vector<T>& v) {
for (auto &x : v) in >> x;
return in;
}
TT
ostream& operator<<(ostream &out, vector<T>& v) {
for (auto &x : v) out << x << ' ';
return out;
}
TT
istream& operator>>(istream &in, pair<T, T>& p) {
in >> p.f >> p.s;
return in;
}
#include <vector>
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R);
const int MAX_N = (1 << 20);
pii T[MAX_N * 2];
void build(vector<int> &a) {
for (int i = 0; i < (int)a.size(); ++i) {
T[MAX_N + i] = mp(a[i], i);
}
for (int i = (int)a.size(); i < MAX_N; ++i) {
T[MAX_N + i] = mp(-1, 0);
}
for (int i = MAX_N - 1; i > 0; --i) {
T[i] = max(T[i * 2], T[i * 2 + 1]);
}
}
void upd(int i, int x) {
i += MAX_N;
T[i] = mp(x, i - MAX_N);
while (i > 1) {
i /= 2;
T[i] = max(T[i * 2], T[i * 2 + 1]);
}
}
pii get(int l, int r) {
l += MAX_N;
r += MAX_N;
pii ans = mp(-1, 0);
while (l < r) {
if (l & 1) {
ans = max(ans, T[l]);
++l;
}
if (r & 1) {
--r;
ans = max(ans, T[r]);
}
l /= 2;
r /= 2;
}
return ans;
}
struct Node {
Node *l, *r;
ll x;
int y, sz;
bool hasSet;
ll setA, setB;
ll addA, addB;
Node(ll x = 0) : l(nullptr), r(nullptr), x(x), y(rnd()), sz(1),
hasSet(false), setA(0), setB(0), addA(0), addB(0) {}
};
int getSz(Node *root) {
return root ? root->sz : 0;
}
void upd(Node *root) {
if (root) root->sz = getSz(root->l) + getSz(root->r) + 1;
}
void apply_set(Node *root, ll a, ll b) {
if (!root) return;
root->x = a + b * getSz(root->l);
root->hasSet = true;
root->setA = a;
root->setB = b;
root->addA = 0;
root->addB = 0;
}
void apply_add(Node *root, ll a, ll b) {
if (!root) return;
root->x += a + b * getSz(root->l);
if (root->hasSet) {
root->setA += a;
root->setB += b;
} else {
root->addA += a;
root->addB += b;
}
}
void push(Node *root) {
if (!root) return;
if (root->hasSet) {
apply_set(root->l, root->setA, root->setB);
apply_set(root->r, root->setA + root->setB * (getSz(root->l) + 1), root->setB);
root->hasSet = false;
root->setA = root->setB = 0;
}
if (root->addA != 0 || root->addB != 0) {
apply_add(root->l, root->addA, root->addB);
apply_add(root->r, root->addA + root->addB * (getSz(root->l) + 1), root->addB);
root->addA = root->addB = 0;
}
}
Node *merge(Node *a, Node *b) {
if (!a) return b;
if (!b) return a;
if (a->y > b->y) {
push(a);
a->r = merge(a->r, b);
upd(a);
return a;
} else {
push(b);
b->l = merge(a, b->l);
upd(b);
return b;
}
}
pair<Node*, Node*> split(Node *root, pair<ll, ll> line) {
if (!root) {
return mp(root, root);
}
push(root);
if (root->x < line.f + line.s * getSz(root->l)) {
auto p = split(root->l, line);
root->l = p.s;
upd(root);
return mp(p.f, root);
} else {
auto p = split(root->r, mp(line.f + line.s * (getSz(root->l) + 1), line.s));
root->r = p.f;
upd(root);
return mp(root, p.s);
}
}
ll get(Node *root, int sz) {
assert(root);
push(root);
if (sz == getSz(root->l)) {
return root->x;
}
if (sz > getSz(root->l)) {
return get(root->r, sz - getSz(root->l) - 1);
}
return get(root->l, sz);
}
void go(Node *root) {
if (!root) return;
push(root);
go(root->l);
cout << root->x << ' ';
go(root->r);
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> L,
std::vector<int> R) {
build(h);
int n = (int)h.size();
vector<ll> ans(L.size());
vector<vector<int>> asked(n);
for (int i = 0; i < (int)L.size(); ++i) {
++R[i];
pii p = get(L[i], R[i]);
ans[i] = p.f * 1ll * (R[i] - L[i]);
asked[p.s].pb(i);
}
auto rec = [&](int l, int r, auto &&self) -> pair<Node*, Node*> {
if (l == r) {
return {nullptr, nullptr};
} else {
pii m = get(l, r);
auto A = self(l, m.s, self);
auto B = self(m.s + 1, r, self);
for (auto &ind : asked[m.s]) {
int indr = R[ind] - m.s - 1;
if (indr) {
ans[ind] = min(ans[ind], get(B.f, indr - 1) + m.f * 1ll * (m.s - L[ind] + 1));
}
int indl = m.s - L[ind];
if (indl) {
ans[ind] = min(ans[ind], get(A.s, indl - 1) + m.f * 1ll * (R[ind] - m.s));
}
}
auto calc = [&](Node *X, int mid, Node *Y) {
if (X) {
ll ansL = get(X, getSz(X) - 1);
auto p = split(Y, mp(ansL - (getSz(X) - 1) * 1ll * mid, mid));
p.f = merge(new Node(0), p.f);
apply_set(p.f, ansL + mid, mid);
apply_add(p.s, (getSz(X) + 1) * 1ll * mid, 0);
return merge(X, merge(p.f, p.s));
} else {
Y = merge(new Node(0), Y);
apply_add(Y, mid, 0);
return Y;
}
};
return mp(calc(A.f, m.f, B.f), calc(B.s, m.f, A.s));
}
};
rec(0, h.size(), rec);
return ans;
}
#ifdef LOCAL
#include <cstdio>
#include <cstdlib>
#include <vector>
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() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
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);
for (size_t j = 0; j < C.size(); ++j) {
printf("%lld\n", C[j]);
}
cout.flush();
return 0;
}
#endif
