#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MX = 505;

int p[MAXN];
int next_le[MX][MAXN];
int next_ge[MX][MAXN]; 
long long memo[MX][MX];
bool c[MX][MX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q; cin >> n >> q;

    for (int i = 0; i < n; ++i)cin >> p[i];


    for (int v = 1; v <= 500; ++v) {
        int last = -1;
        next_le[v][n] = -1;
        for (int i = n - 1; i >= 0; --i) {
            if (p[i] <= v) last = i;
            next_le[v][i] = last;
        }
    }

    for (int e = 1; e <= 500; ++e) {
        int last = -1;
        next_ge[e][n] = -1;
        for (int i = n - 1; i >= 0; --i) {
            if (p[i] >= e) last = i;
            next_ge[e][i] = last;
        }
    }


    while (q--) {
        int v, e;cin >> v >> e;

        if (c[v][e]) {
            cout << memo[v][e] << "\n";
            continue;
        }

        long long ans = 0;
        int t = 0;

        while (t < n) {
            int idx = next_le[v][t];
            if (idx == -1) break;

            ans -= p[idx];

            idx = next_ge[e][idx + 1];
            if (idx == -1) break;

            ans += p[idx];
            t = idx + 1;
        }

        c[v][e] = true;
        memo[v][e] = ans;
        cout << ans << "\n";
    }

    return 0;
}