#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int MAXN = 10'001;

int a[MAXN], ans[501][501];
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>> points;
        for (int i = 1; i <= n; i++) {
            if (a[i] <= l) {
                points.insert({i, true});
            }
        }
        if (points.empty()) continue;
        int idx = points.begin()->first;
        int cost = a[idx];
        for (int r = 500; r >= l+1; r--) {
            for (int i : pos[r]) {
                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()) {
                            cost += a[nxt->first];
                            if (!nxt->second) {
                                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;
}