#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int MAXN = 10'001;

int a[MAXN], ans[MAXN][MAXN];
vector<int> pos[501];

void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]].emplace_back(i);
    }
    for (int l = 1; l <= 500; l++) {
        set<pair<int, bool>> indices, points;
        for (int i = 1; i <= n; i++) {
            if (a[i] <= l) {
                indices.insert({i, false});
                points.insert({i, true});
            }
        }
        if (indices.empty()) continue;
        int idx = indices.begin()->first;
        indices.erase(indices.begin());
        int cost = a[idx];
        indices.insert({idx, true});
        for (int r = 500; r >= l+1; r--) {
            for (int i : pos[r]) {
                auto it = indices.lower_bound({i, false});
                if (it != indices.end() && !it->second) {
                    idx = it->first;
                    indices.erase(it);
                    indices.insert({idx, true});
                    cost += a[idx];
                }

                auto bef = points.lower_bound({i, false});
                if (bef != points.begin()) {
                    bef--;
                    if (bef->second) {
                        cost -= a[i];
                        auto nxt = points.lower_bound({i, false});
                        if (nxt != points.end() && !nxt->second) {
                            cost += a[nxt->first];
                            points.erase(nxt);
                        }
                        points.insert({i, false});
                    }
                }
                
            }
            ans[l][r] = cost;
        }
    }
    while (m--) {
        int a, b; cin >> a >> b;
        cout << -ans[a][b] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}