#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
const int N = 750100;
int n, q;
int H[N];
pair<int, int> sp[20][N];
pair<int, int> spmax(int l, int r, int id)
{
int len = r - l + 1;
int jj = H[len];
if (id == 0)
{
return max(sp[jj][l], sp[jj][r - (1 << jj) + 1]);
}
else
{
if (sp[jj][l].first != sp[jj][r - (1 << jj) + 1].first)
return max(sp[jj][l], sp[jj][r - (1 << jj) + 1]);
else
return min(sp[jj][l], sp[jj][r - (1 << jj) + 1]);
}
}
bool comp1(pair<int, int> a, pair<int, int> b)
{
if (a.first != b.first)
return a < b;
else
return a > b;
}
struct Linear{
int k;
long long b;
};
struct Node{
Linear line;
int func;
long long addition;
};
Node tree[4 * N];
void Push(int V, int L, int R, int M)
{
if (tree[V].func)
{
tree[2 * V + 1].func = 1;
tree[2 * V + 1].addition = 0;
tree[2 * V + 2].func = 1;
tree[2 * V + 2].addition = 0;
tree[2 * V + 1].line.b = tree[V].line.b;
tree[2 * V + 1].line.k = tree[V].line.k;
tree[2 * V + 2].line.b = tree[V].line.b + 1LL * (M - L) * tree[V].line.k;
tree[2 * V + 2].line.k = tree[V].line.k;
tree[V].func = 0;
}
else
{
if (tree[2 * V + 1].func)
{
tree[2 * V + 1].line.b += tree[V].addition;
}
else
{
tree[2 * V + 1].addition += tree[V].addition;
}
if (tree[2 * V + 2].func)
{
tree[2 * V + 2].line.b += tree[V].addition;
}
else
{
tree[2 * V + 2].addition += tree[V].addition;
}
tree[V].addition = 0;
}
}
long long Get(int p, int L = 0, int R = n, int V = 0)
{
if (tree[V].func)
{
return tree[V].line.b + 1LL * (p - L) * tree[V].line.k;
}
if (L + 1 == R)
{
return tree[V].addition;
}
int M = (L + R) / 2;
Push(V, L, R, M);
if (p < M) return Get(p, L, M, 2 * V + 1);
return Get(p, M, R, 2 * V + 2);
}
void Add(int l, int r, long long val, int L = 0, int R = n, int V = 0)
{
if (r <= L || R <= l)
{
return;
}
if (l <= L && R <= r)
{
if (tree[V].func) tree[V].line.b += val;
else tree[V].addition += val;
return;
}
int M = (L + R) / 2;
Push(V, L, R, M);
Add(l, r, val, L, M, 2 * V + 1);
Add(l, r, val, M, R, 2 * V + 2);
}
void Set(int l, int r, long long func_at_l, int k, int L = 0, int R = n, int V = 0)
{
if (r <= L || R <= l)
{
return;
}
if (l <= L && R <= r)
{
tree[V].addition = 0;
tree[V].func = 1;
tree[V].line.k = k;
tree[V].line.b = func_at_l + 1LL * (L - l) * k;
return;
}
int M = (L + R) / 2;
Push(V, L, R, M);
Set(l, r, func_at_l, k, L, M, 2 * V + 1);
Set(l, r, func_at_l, k, M, R, 2 * V + 2);
}
void Reset()
{
for (int i = 0; i < 4 * N; i++)
{
tree[i].func = 0;
tree[i].line.k = 0;
tree[i].line.b = 0;
tree[i].addition = 0;
}
}
vector<long long> solve(vector<int> h, vector<int> l, vector<int> r, int id)
{
if (id) Reset();
vector<int> active(n);
vector<long long> re_ans(q);
vector<pair<long long, int> > order;
for (int i = 0; i < n; i++)
{
order.push_back({h[i], i});
}
if (id == 0) sort(order.begin(), order.end());
else sort(order.begin(), order.end(), comp1);
for (int i = 0; i < n; i++)
{
sp[0][i] = {h[i], i};
}
for (int j = 1; j < 20; j++)
{
for (int i = 0; i + (1 << j) - 1 < n; i++)
{
sp[j][i] = spmax(i, i + (1 << j) - 1, id);
}
}
vector<vector<int> > queries_here(n);
for (int j = 0; j < q; j++)
{
queries_here[spmax(l[j], r[j], id).second].push_back(j);
}
#ifdef LOCAL
cout << "Solution\n";
#endif // LOCAL
vector<int> LL(n), RR(n);
for (auto it : order)
{
int L = 0, R = n - 1;
active[it.second] = 1;
#ifdef LOCAL
for (int i = 0; i < n; i++) cout << Get(i) << " ";
cout << "\n";
#endif // LOCAL
for (int i = 0; i < queries_here[it.second].size(); i++)
{
int j = queries_here[it.second][i];
re_ans[j] = Get(r[j]) + 1ll * (it.second - l[j] + 1) * it.first;
}
{
int i = it.second;
if (i > 0 && active[i - 1] == 1)
L = LL[i - 1];
if (i > 0 && active[i - 1] == 0)
L = i;
if (i + 1 < n && active[i + 1] == 1)
R = RR[i + 1];
if (i + 1 < n && active[i + 1] == 0)
R = i;
}
RR[L] = R;
LL[R] = L;
long long cnt = it.second - L + 1;
Add(it.second, R + 1, cnt * it.first);
#ifdef LOCAL
cout << "add call " << it.second << " " << R << " " << cnt * it.first << "\n";
#endif // LOCAL
if (it.second > 0 && active[it.second - 1] == 1)
{
int le = it.second - 1;
int ri = R + 1;
long long kek = Get(it.second - 1);
while (le + 1 < ri)
{
int rr = (le + ri) / 2;
if (Get(rr) > kek + (rr - it.second + 1) * it.first) le = rr;
else ri = rr;
}
Set(it.second, le + 1, Get(it.second - 1) + it.first, it.first);
#ifdef LOCAL
cout << "set call " << it.second << " " << le << " " << Get(it.second - 1) + it.first << " " << it.first << "\n";
#endif
}
}
return re_ans;
}
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r)
{
H[1] = 0, H[2] = 0, H[3] = 1;
for (int i = 4; i < N; i++)
{
H[i] = H[i - 1];
if (((i - 1) & (i - 2)) == 0)
{
H[i]++;
}
}
n = h.size(), q = l.size();
vector<long long> res1 = solve(h, l, r, 0);
reverse(h.begin(), h.end());
for (int i = 0; i < q; i++)
{
l[i] = n - l[i] - 1;
r[i] = n - r[i] - 1;
swap(l[i], r[i]);
}
vector<long long> res2 = solve(h, l, r, 1);
vector<long long> ans(q);
for (int i = 0; i < q; i++)
{
ans[i] = min(res1[i], res2[i]);
}
#ifdef LOCAL
for (int i = 0; i < q; i++) cout << res1[i] << " "; cout << "\n";
for (int i = 0; i < q; i++) cout << res2[i] << " "; cout << "\n";
#endif // LOCAL
return ans;
}
#ifdef LOCAL
int main()
{
int n, q;
cin >> n >> q;
vector<int> h(n);
vector<int> l(q), r(q);
for (int i = 0; i < n; i++) cin >> h[i];
for (int i = 0; i < q; i++) cin >> l[i] >> r[i];
vector<long long> ans = minimum_costs(h, l, r);
for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}
#endif // LOCAL
