/*
    ID : thoria1991
    TASK : barn1
    LANG : C++11
*/

#include <bits/stdc++.h>

#define N 100002
#define sqrtN 350
#define ll long long
#define INF (ll)(2e17)

using namespace std;

struct Hunk{

    ll  best = -INF, 
        minSum = INF, 
        maxSum = INF;
} hunks[sqrtN];

ll sum[N], best[sqrtN][sqrtN];
int k;

Hunk BuildData(int st, int end){

    Hunk hunk;
    ll s = 0;
    for(int i = st; i <= end; i ++){

        hunk.maxSum = max(hunk.maxSum, sum[i]);
        hunk.minSum = min(hunk.minSum, sum[i - 1]);

        if(s < 0) s = 0;
        s += sum[i] - sum[i - 1];

        hunk.best = max(hunk.best, s);
    }

    return hunk;
}

ll Solve(int x, int y){

    int xHunkNum = x / k + (x % k != 0) ? 1 : 0;
    int yHunkNum = y / k + (y % k != 0) ? 1 : 0;

    if(xHunkNum == yHunkNum)
        return BuildData(x, y).best;

    Hunk xHunk = BuildData(x, xHunkNum * k);
    Hunk yHunk = BuildData((yHunkNum - 1) * k + 1, y);

    ll best = max(::best[xHunkNum + 1][yHunkNum - 1], yHunk.maxSum - xHunk.minSum);
    for(int i = xHunkNum + 1; i <= yHunkNum; i ++)
        best = max(best, hunks[i].maxSum - xHunk.minSum),
        best = max(best, yHunk.maxSum - hunks[i].minSum);

    return best;
}

int main(){

    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);

    int n, m;
    scanf("%d%d", &n, &m);
    k = sqrt(n);

    for(int i = 1; i <= n; i ++){

        scanf("%lld", &sum[i]);
        sum[i] += sum[i - 1];
    }

    for(int i = 1; i <= k; i ++){

        int pMin = (i - 1) * k + 1;
        int pMax = min(i * k, n);

        hunks[i] = BuildData(pMin, pMax);
    }

    for(int i = 1; i <= k; i ++){

        ll minSum  = hunks[i].minSum;
        ll maxSum  = -INF;
        best[i][i] = best[i][i - 1] = -INF;

        for(int j = i + 1; j <= k; j ++){

            maxSum = max(maxSum, hunks[j].maxSum);
            minSum = min(minSum, hunks[j].minSum);
            best[i][j] = maxSum - minSum;
        }
    }

    for(int i = 1; i <= m; i ++){

        int x, y;
        scanf("%d%d", &x, &y);
        printf("%lld\n", Solve(x, y));
    }
}