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

#define int long long

signed main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    vector<vector<pair<int, int>>> dpv(501), dpe(501);
    //stat: 1:mar johet a kovi vetel (k feletti reszben vagyunk mar) 0: meg nem jott k-nal magasabb a legutobbi vetel ota
    for (int k = 1; k <= 500; k++) {
        int stat = 1, maxi = 501;
        for (int i = 1; i <= n; i++) {
            if (stat==1&&v[i]<=k) {
                dpv[k].push_back({maxi, -v[i]});
                stat=0;
                maxi=0;
            } else if (stat==1) {
                maxi=max(maxi,v[i]);
            } else if (stat==0&&v[i]>k) {
                maxi=v[i];
                stat=1;
            }
            if (k==40) {
                // cout << i << ": " << stat << ' ' << maxi << endl;
            }
        }
        sort(dpv[k].begin(), dpv[k].end());
        dpv[k].push_back({502, 0});
        int m = dpv[k].size();
        for (int i = m-2; i >= 0; i--) {
            dpv[k][i]={dpv[k][i].first, dpv[k][i].second+dpv[k][i+1].second};
        }
    }
    //stat: 1: mar johet az eladas (szval k alatti reszben voltunk eddig), 0: eddig nem jott knal nagyobb egyenlo
    for (int k = 1; k <= 500; k++) {
        int stat = 0, mini = 501;
        for (int i = 1; i <= n; i++) {
            if (stat==1&&v[i]>=k) {
                dpe[k].push_back({mini, v[i]});
                stat=0;
                mini=501;
            } else if (stat==1) {
                mini=min(mini,v[i]);
            } else if (stat==0&&v[i]<k) {
                mini=v[i];
                stat=1;
            }
            if (k==120) {
                //cout << i << ": " << stat << ' ' << mini << endl;
            }
        }
        dpe[k].push_back({0, 0});
        sort(dpe[k].begin(), dpe[k].end());
        int m = dpe[k].size();
        for (int i = 1; i < m; i++) {
            dpe[k][i] = {dpe[k][i].first, dpe[k][i].second + dpe[k][i-1].second};
        }
    }
    // for (int i = 0; i < dpv[40].size(); i++)cout<<dpv[40][i].first << ' ' << dpv[40][i].second << endl;
    // for (int i = 0; i < dpe[120].size(); i++)cout<<dpe[120][i].first << ' ' << dpe[120][i].second << endl;
    while (q--) {
        int a, b;
        cin >> a >> b;
        auto it = upper_bound(dpe[b].begin(), dpe[b].end(), make_pair(a, 501LL));
        it--;
        cout << it->second + lower_bound(dpv[a].begin(), dpv[a].end(), make_pair(b, -501LL))->second << endl;
        // cout << a << ' ' << b << ' ' << lower_bound(dpv[a].begin(), dpv[a].end(), make_pair(b, -502))->second << endl;
    }
}