#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

int read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}

struct Node {
Node *ch[2];
int r, v, s, w;
long long sum;
Node(int v):v(v) { ch[0] = ch[1] = NULL; r = rand(); s = w = 1; sum = v; }
int cmp(int x) {
if (x == v) return -1;
return x < v ? 0 : 1;
}
void push_up() {
s = w;
sum = w * v;
if (ch[0] != NULL) { s += ch[0]->s; sum += ch[0]->sum; }
if (ch[1] != NULL) { s += ch[1]->s; sum += ch[1]->sum; }
}
};

inline void rotate(Node* &rt, int d) {
Node* k = rt->ch[d ^ 1];
rt->ch[d ^ 1] = k->ch[d];
k->ch[d] = rt;
rt->push_up();
k->push_up();
rt = k;
}

void insert(Node* &rt, int x) {
if (rt == NULL) rt = new Node(x);
else {
int d = rt->cmp(x);
if (d == -1) (rt->w)++;
else {
insert(rt->ch[d], x);
if (rt->ch[d]->r > rt->r) rotate(rt, d ^ 1);
}
}
rt->push_up();
}

long long left_num, left_sum;

int kth(Node *rt, int k) {
int d = (rt->ch[0] == NULL ? 0 : rt->ch[0]->s);
if (k <= d) return kth(rt->ch[0], k);
else if (rt->ch[1] != NULL && k > d + rt->w) {
left_num += d + rt->w;
left_sum += (d == 0 ? 0 : rt->ch[0]->sum) + rt->w * rt->v;
return kth(rt->ch[1], k - d - rt->w);
} else {
if (d) left_sum += rt->ch[0]->sum;
left_num += d;
return rt->v;
}
}

const int N = 1000 + 5;

int n, m, h[N], ans[N][N];

int main() {
#ifdef LOCAL
freopen("C:\Users\Administrator\Desktop\in.txt", "r", stdin);
freopen("C:\Users\Administrator\Desktop\out.txt", "w", stdout);
#endif
n = read(); m = read();
for (int i = 1; i <= n; i++) h[i] = read();
for (int l = 1; l <= n; l++) {
Node* root = NULL;
long long tot = 0;
for (int r = l; r <= n; r++) {
tot += h[r];
insert(root, h[r]);
left_sum = left_num = 0;
int ave = kth(root, (r - l + 2) / 2);
ans[l][r] = left_num * ave - left_sum;
ans[l][r] += tot - left_sum - (r - l - left_num + 1) * ave;
}
delete root;
}
int l, r;
long long res = 0;
while (m--) {
l = read(); r = read();
res += ans[l][r];
}
printf("%lld\n", res);
return 0;
}