#include <fstream>
using namespace std;

const int MAX_N = 100002;
const long long int INF = 999999999999999LL;

int N, M;
int v[MAX_N];
long long int S[MAX_N];
long long int A[2*MAX_N], A1[2*MAX_N], A2[2*MAX_N];

inline void update(int node, int left, int right, int x, long long int sum, int value) {
    if(left == right) {
        A1[node] = A2[node] = sum;
        A[node] = value;
    }
    else {
        int m = (left+right)/2;
        if(x <= m)
            update(2*node, left, m, x, sum, value);
        else update(2*node+1, m+1, right, x, sum, value);
        A1[node] = max(A1[2*node], A1[2*node+1]);
        A2[node] = min(A2[2*node], A2[2*node+1]);
        A[node] = max(A1[2*node+1] - A2[2*node], max(A[2*node], A[2*node+1]));
    }
}

inline long long int query1(int node, int left, int right, int x, int y) {
    if(x <= left && right <= y)
        return A1[node];
    else {
        int m = (left+right)/2;
        long long int temp1, temp2;
        if(x <= m)
            temp1 = query1(2*node, left, m, x, y);
        else temp1 = -INF;
        if(y > m)
            temp2 = query1(2*node+1, m+1, right, x, y);
        else temp2 = -INF;

        return max(temp1, temp2);
    }
}

inline long long int query2(int node, int left, int right, int x, int y) {
    if(x <= left && right <= y)
        return A2[node];
    else {
        int m = (left+right)/2;
        long long int temp1, temp2;
        if(x <= m)
            temp1 = query2(2*node, left, m, x, y);
        else temp1 = INF;
        if(y > m)
            temp2 = query2(2*node+1, m+1, right, x, y);
        else temp2 = INF;

        return min(temp1, temp2);
    }
}

inline long long int query(int node, int left, int right, int x, int y) {
    if(x <= left && right <= y)
        return A[node];
    else {
        int m = (left+right)/2;
        long long int temp1, temp2, temp3;
        if(x <= m)
            temp1 = query(2*node, left, m, x, y);
        else temp1 = -INF;
        if(y > m)
            temp2 = query(2*node+1, m+1, right, x, y);
        else temp2 = -INF;
        if(x <= m && y > m)
            temp3 = query1(1, 1, N, m+1, y) - query2(1, 1, N, x, m);
        else temp3 = -INF;

        return max(temp3, max(temp1, temp2));
    }
}



int main() {
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");

    f >> N >> M;
    for(int i = 1; i <= N; ++i) {
        f >> v[i];
        S[i] = v[i] + S[i-1];
        update(1, 1, N, i, S[i], v[i]);
    }


    for(int i = 1, x, y; i <= M; ++i) {
        f >> x >> y;
        g << query(1, 1, N, x, y) << "\n";
    }

    f.close();
    g.close();

    return 0;
}