#include <bits/stdc++.h>
#define MAXN 100000
#define MAXVAL 10000000000

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

long long aint_min[4 * MAXN], aint_max[4 * MAXN];
long long sp[MAXN + 1];

void build_max(int nod, int st, int dr){
    int mij;

    if(st == dr){
        aint_max[nod] = sp[st];
    }else{
        mij = (st + dr) / 2;
        build_max(2 * nod, st, mij);
        build_max(2 * nod + 1, mij + 1, dr);
        aint_max[nod] = max(aint_max[2 * nod], aint_max[2 * nod + 1]);
    }
}
void build_min(int nod, int st, int dr){
    int mij;

    if(st == dr){
        aint_min[nod] = sp[st];
    }else{
        mij = (st + dr) / 2;
        build_min(2 * nod, st, mij);
        build_min(2 * nod + 1, mij + 1, dr);
        aint_min[nod] = min(aint_min[2 * nod], aint_min[2 * nod + 1]);
    }
}
long long query_max(int nod, int st, int dr, int a, int b){
    int mij;

    if(st > b || dr < a){
        return 0;
    }
    if(st >= a && dr <= b){
        return aint_max[nod];
    }
    mij = (st + dr) / 2;
    return max(query_max(2 * nod, st, mij, a, b), query_max(2 * nod + 1, mij + 1, dr, a, b));
}
long long query_min(int nod, int st, int dr, int a, int b){
    int mij;

    if(st > b || dr < a){
        return MAXVAL;
    }
    if(st >= a && dr <= b){
        return aint_min[nod];
    }
    mij = (st + dr) / 2;
    return min(query_min(2 * nod, st, mij, a, b), query_min(2 * nod + 1, mij + 1, dr, a, b));
}

int main()
{
    int n, m, i, x, y;

    fin >> n >> m;
    for(i = 1; i <= n; i++){
        fin >> sp[i];
        sp[i] += sp[i - 1];
    }
    build_max(1, 1, n);
    build_min(1, 1, n);

    while(m--){
        fin >> x >> y;

        fout << query_max(1, 1, n, x, y) - query_min(1, 1, n, x-1, y-1) << "\n";
    }
    return 0;
}