#include <bits/stdc++.h>
#define BT ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define ll long long
#define MAXN 100010
using namespace std;
int n, q, a, b, arr[MAXN], sum1[MAXN], sum2[MAXN];
int main() {
BT cin >> n >> q;
int i, j, k;
for (i = 0; i < n; i++) cin >> arr[i];
for (i = 0, j = 1, k = 1; i < n; i++, j++, k++) {
while (j < arr[i]) {
sum1[j] = sum1[j - 1];
j++;
}
sum1[j] = arr[i] + sum1[j - 1];
while (k < arr[i]) {
sum2[k] = sum2[k - 1];
k++;
}
sum2[k] = sum2[k - 1] + 1;
}
while (q--) {
cin >> a >> b;
if (a > b) a += b, b = a - b, a -= b;
int t = (a + b) / 2;
ll sum = (a * sum2[a] - sum1[a]) +
((sum1[t] - sum1[a]) - a * (sum2[t] - sum2[a])) +
(b * (sum2[b] - sum2[t]) - (sum1[b] - sum1[t])) +
((sum1[j - 1] - sum1[b]) - b * (sum2[k - 1] - sum2[b]));
cout << sum << endl;
}
return 0;
} 