/*
    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;

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

struct Hunk{

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

ll sum[N];
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);

    Hunk leftHunk = hunks[xHunkNum];
    Hunk rightHunk = hunks[yHunkNum];

    hunks[xHunkNum] = xHunk;
    hunks[yHunkNum] = yHunk;

    ll best = xHunk.best;
    for(int i = xHunkNum; i <= yHunkNum; i ++){
        
        best = max(best, hunks[i].best);
        for(int j = i + 1; j <= yHunkNum; j ++)
            best = max(best, hunks[j].maxSum - hunks[j].minSum);
    }
    
    hunks[xHunkNum] = leftHunk;
    hunks[yHunkNum] = rightHunk;

    return best;
}

int main(){
    
    int n, m;
    fin >> n >> m; 
    k = sqrt(n);

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

        fin >> 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 <= m; i ++){

        int x, y;
        fin >> x >> y;
        fout << Solve(x, y) << '\n';
    }
}