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

const int MAXN = 10005;
const int MAXVAL = 505;


short p[MAXN];
short next_le[MAXVAL][MAXN];
short next_ge[MAXVAL][MAXN];

int memo[MAXVAL][MAXVAL];
bool c[MAXVAL][MAXVAL];

int main() {
    ios_base::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 < MAXVAL; ++v) {
        int last = -1;
        for (int i = N - 1; i >= 0; --i) {
            if (p[i] <= v) last = i;
            next_le[v][i] = (short)last;
        }
        next_le[v][N] = -1; 
    }

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

    for (int q = 0; q < Q; ++q) {
        int V, E;cin >> V >> E;

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

        int ans = 0;
        int t = 0;
        
        const short* n_le = next_le[V];
        const short* n_ge = next_ge[E];

        while (t < N) {
            int idx = n_le[t];
            if (idx == -1) break;

            ans -= p[idx];

            if (idx + 1 >= N) break;
            
            idx = n_ge[idx + 1];
            if (idx == -1) break;

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

        memo[V][E] = ans;
        c[V][E] = true;
        cout << ans << "\n";
    }

    return 0;
}