#include <iostream>
#include <vector>
using namespace std;

vector<int> e[501], v[501];
int n, a[10000], x, y, q;

int main()
{
    cin >> n >> q;
    for(int i=1; i<=500; i++){
        e[i].push_back(-1);
        v[i].push_back(-1);
    }
    for(int i=0; i<n; i++){
        cin >> a[i];
        for(int j=1; j<=500; j++){
            if(j>=a[i]){
                v[j].push_back(i);
            }
            if(j<=a[i]){
                e[j].push_back(i);
            }
        }
    }
    while(q--){
        int haszon=0;
        cin >> x >> y;
        int i=0, j=0; //i- vetele indexe, j - eladas indexe
        bool van=0;
        int maxi=v[x].size(), maxj=e[y].size();
        while(i<maxi&&j<maxj){
            /*cout << "i: " << i << '\n';
            cout << "j: " << j << '\n';
            cout << "v[x][i]: " << v[x][i] << '\n';
            cout << "e[y][j]: " << e[y][j] << '\n';*/
            if(van){
                do{
                    j++;
                }while (j<maxj&&e[y][j]<=v[x][i]);
                if(j<maxj){
                    //cout << "eladott " << a[e[y][j]] << "-ert\n";
                    haszon+=a[e[y][j]];
                    van=0;
                }
            }
            else{
                do{
                    i++;
                }while(i<maxi&&v[x][i]<=e[y][j]);
                if(i<maxi){
                    //cout << "vett " << a[v[x][i]] << "-ert\n";
                    haszon-=a[v[x][i]];
                    van=1;
                }
            }
        }
            /*cout << "i: " << i << '\n';
            cout << "j: " << j << '\n';
        for(auto& it:v[x]){
            cout << it << ' ';
        }
        cout << '\n';
        for(auto& it:e[y]){
            cout << it << ' ';
        }
        cout << '\n';*/
        cout << haszon << '\n';
    }

    //cout << e[40][2] << '\n';
    return 0;
}