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

#ifdef DEBUG
ifstream in_file("C:\\verseny\\minta\\be1.txt");
#define input in_file
#define INTHENAMEOFGOD
#else
#define input cin
#define INTHENAMEOFGOD \
    ios::sync_with_stdio(0); \
    cin.tie(0); \
    cout.tie(0);
#endif
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<ll, ll> pii;

ll N, Q, V, E, x;
vector<vb> vvb;
vvi h;

int main() {
    INTHENAMEOFGOD
    input >> N >> Q;

    vvb = vector<vb>(500, vb(500, false));
    h = vvi(500, vi(500, 0));
    for (ll n = 0; n < N; n++) {
        input >> x;
        for (V = 0; V < 499; V++) {
            for (E = V+1; E < 500; E++) {
                if (vvb[V][E]) {
                    if (x >= E + 1) {
                        h[V][E] += x;
                        vvb[V][E] = false;
                    }
                } else {
                    if (x <= V + 1) {
                        h[V][E] -= x;
                        vvb[V][E] = true;
                    }
                }
            }
        }
    }
    for (ll q = 0; q < Q; q++) {
        input >> V >> E;
        V--; E--;
        cout << h[V][E] << "\n";
    }
}