/*
    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, nrHunks;
 
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);
    int yHunkNum = y / k + (y % k != 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);
    best = max(best, max(xHunk.best, yHunk.best));

    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);
    nrHunks = n / k + (n % k != 0);
 
    for(int i = 1; i <= n; i ++){
 
        scanf("%lld", &sum[i]);
        sum[i] += sum[i - 1];
    }
 
    for(int i = 1; i <= nrHunks; i ++){
 
        int pMin = (i - 1) * k + 1;
        int pMax = min(i * k, n);
 
        hunks[i] = BuildData(pMin, pMax);
    }
 
    for(int i = 1; i <= nrHunks; i ++){
 
        ll minSum  = hunks[i].minSum;
        ll maxSum  = -INF;
        best[i][i] = best[i][i - 1] = -INF;
 
        for(int j = i + 1; j <= nrHunks; j ++){
 
            maxSum = max(maxSum, hunks[j].maxSum);
            best[i][j] = maxSum - minSum;
            minSum = min(minSum, hunks[j].minSum);
        }
    }
 
    for(int i = 1; i <= m; i ++){
 
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%lld\n", Solve(x, y));
    }
}