#include <bits/stdc++.h>

using ll = long long;
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

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<int> points;
        for (int i = 1; i <= n; i++) {
            if (a[i] <= l) {
                points.insert(i);
            }
        }
        if (points.empty()) continue;
        int cost = -a[*points.begin()];
        for (int r = 500; r >= l+1; r--) {
            for (int i : pos[r]) {
                if (*points.begin() < i) {
                    auto bef = points.lower_bound(i);
                    bef--;
                    if (a[*bef] <= l) {
                        cost += a[i];
                        auto nxt = points.lower_bound(i);
                        if (nxt != points.end()) {
                            cost -= a[*nxt];
                            if (a[*nxt] > l) {
                                points.erase(nxt);
                            }
                        }
                        points.insert(i);
                    }
                }
            }
            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;
}