/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author Azat Ismagilov
*/
/*.. ....
..',,'..............''...'''.','..
.';'.. ..',,'.
.'.. .';,.
.'. .:ol;. .';.
.. .cO00k:. .,.
.. .'...;k00Od' .'.
... .;xOkxdk00Od, ...
... .,x0000000Od;. ..
.' .cO00OOOOOOd;'... ...
.'. .;lxkOOOO00Okkxo:. .'.
.'. .cxOOOOO000000Ol. .'.
.'. .ck00OOd::oxOOOOl. .,.
''...,;''''''''':kKK0Od,. ..:xOo' .,.
';,;;;:,..........;lxOx:. .';' .''
'cc;.. .,;:,.. ...
,oc. .......... .',:;,.. ...
'o:. .,;;;,,,,;;;;;'. ..,;;,.. ...
';. ... .,::. .,::'. .'.
.. .',. ..;;'. ...
.. .',,;;,'. ':;'. .,.
.,::;,. ....... .';:'. .,,.
.;dOK0x;. . .':;. .,.
...,cdxdl;. ..,;;;cloddoc;. .,:,. .,.
. ...;cl:. ':ldxxdocccclol;. ..:;.',.
. .;llc;',c;. .,:,''';::;'. .. .;:;'
.:xdoxko,',. .,:. .;llc:ldl. .;c.
.lxdoxkd:''. .;:. .cxl'';od;. .. .,,
.:clool;.',. .:' .:dxolccl;. .::;,:'
.;::,.. .,. .;. .,:;:;,,;' .,;,:ol.
.. ',. .;. .',,,,,. .,:llc;.
.,' .,. .;lxxc'
.,;. .;. .;lxxc.
.. .;;. .:' .;cc,.
...';' .;;. .;:. ,:'
.;c:;. .. .,;. ....,;. .'.
.,lc,. .':,..,:,''....;c:;'':'.. .. .'.
.;:;. .,:' .::,,;;;;;..',;,..,,. .,. .'.
.'',,. .,;. .;, .'. ...
.'',,. .,;. ';. .,. .'.
.'... .;. .,,. .,' ..
.'. .;,. .::. .,' .
.'. .,;. ,c' .,' .'.
.'. .:' .,' .. .,'
''. ,;. ..................... .;' .:,
.,. .,;. ..'''''''''''''''''','. .,;. .::.
.,. ,;. .,;. .;,.
.,,. .:,. .;;. .''.
.,' .'. ... .,.
.'' .,.
.,'. .'.
.'. .*/
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <set>
#include <map>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define eb emplace_back
#define mp make_pair
#define len(v) ((int)v.size())
#define vc vector
#define pr pair
#define all(v) v.begin(), v.end()
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
template<typename T, typename U>
inline ostream &operator<<(ostream &_out, const pair<T, U> &_p) {
_out << _p.first << ' ' << _p.second;
return _out;
}
template<typename T, typename U>
inline istream &operator>>(istream &_in, pair<T, U> &_p) {
_in >> _p.first >> _p.second;
return _in;
}
template<typename T>
inline ostream &operator<<(ostream &_out, const vector<T> &_v) {
if (_v.empty()) { return _out; }
_out << _v.front();
for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; }
return _out;
}
template<typename T>
inline istream &operator>>(istream &_in, vector<T> &_v) {
for (auto &_i : _v) { _in >> _i; }
return _in;
}
const int MAXN = 2e5 + 10;
const int INF = 1e9;
const int MOD = 1e9 + 7;
vc<pr<pr<int, int>, pr<int, int>>> lefts, rights;
void add_segment(int l1, int r1, int l2, int r2, int value) {
//cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << ' ' << value << endl;
if (r1 - l1 <= r2 - l2) {
for (int i = l1; i <= r1; i++) {
lefts.pb({{i, value},
{l2 - i, r2 - i}});
}
} else {
for (int i = l2; i <= r2; i++) {
rights.pb({{i, value},
{i - r1, i - l1}});
}
}
}
int n;
ll t[MAXN];
void init(int nn) {
n = nn;
fill(t, t + n, 0);
}
void upd(int v, int x) {
for (; v < n; v = (v | (v + 1))) {
t[v] += x;
}
}
ll get(int v) {
ll ans = 0;
for (; v >= 0; v = (v & (v + 1)) - 1) {
ans += t[v];
}
return ans;
}
ll get(int l, int r) {
return get(r) - get(l - 1);
}
class pozhar {
public:
void solve(std::istream &in, std::ostream &out) {
int n, q;
in >> n >> q;
vc<int> s(n);
in >> s;
set<int> limiters;
limiters.insert(-1);
limiters.insert(n);
vc<pr<int, int>> dds;
for (int i = 0; i < n; i++) {
dds.pb({s[i], i});
}
sort(all(dds));
reverse(all(dds));
for (auto v : dds) {
auto r = (*limiters.lower_bound(v.sc)) - 1;
auto l = (*prev(limiters.lower_bound(v.sc))) + 1;
if (l <= v.sc && v.sc <= r) {
add_segment(l, v.sc, v.sc, r, v.fs);
}
limiters.insert(v.sc);
}
/*
cout << "lefts\n";
for (auto v : lefts) {
cout << v << endl;
}
cout << "rights\n";
for (auto v : rights) {
cout << v << endl;
}
*/
vc<ll> ans(q);
vc<pr<int, pr<int, int>>> que(q);
vc<vc<int>> bylen(n + 2);
int i = 0;
for (auto &v : que) {
in >> v.fs >> v.sc;
v.sc.fs--, v.sc.sc--;
bylen[v.fs].pb(i);
i++;
}
{
int maxi = 0;
for (int i = 0; i < n; i++) {
maxi = max(maxi, s[i]);
rights.pb({{i, maxi},
{i + 1, n}});
}
}
{
vc<vc<pr<int, int>>> gr(n + 2);
for (auto v : lefts) {
gr[v.sc.fs].pb(v.fs);
v.fs.sc *= -1;
gr[v.sc.sc + 1].pb(v.fs);
}
init(n + 10);
for (int i = 0; i <= n; i++) {
for (auto d : gr[i]) {
upd(d.fs, d.sc);
}
for (auto d : bylen[i]) {
ans[d] += get(que[d].sc.fs - i, que[d].sc.sc - i);
}
}
}
{
vc<vc<pr<int, int>>> gr(n + 2);
for (auto v : rights) {
gr[v.sc.fs].pb(v.fs);
v.fs.sc *= -1;
gr[v.sc.sc + 1].pb(v.fs);
}
init(n + 10);
for (int i = 0; i <= n; i++) {
for (auto d : gr[i]) {
upd(d.fs, d.sc);
}
for (auto d : bylen[i]) {
ans[d] += get(que[d].sc.fs, que[d].sc.sc);
}
}
}
for (auto v : ans) {
out << v << '\n';
}
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
pozhar solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
