#include <fstream>
using namespace std;
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
// Observation : No updates.
// Idea for combining
/*
There are 3 options if we consider consecutive intervals A and B
1) Take biggest subsequence from A
2) Take biggest subsequence from B
3) Take the biggest suffix from A with the biggest prefix from B
Taking the max of these will get us the biggest subsequence.
*/
typedef long long ll;
const int mxN = 1e5;
ll n , m;
ll sol, suf;
struct node
{ll totalSum,sum,prefix,suffix; }A[4*mxN+1];
void build(int node, int st, int dr)
{
    if(st == dr)
    {
        int x; cin >> x;
        A[node] = {x, x, x, x};
        return;
    }
    int mid = (st + dr) / 2;
    build(2*node,st,mid);
    build(2*node+1,mid+1,dr);
    // Calculate A[node] total sum
    A[node].totalSum = A[2*node].totalSum + A[2*node+1].totalSum;
    // Calculate biggest prefix of A[node]
    A[node].prefix = max(A[2*node].prefix, A[2*node].totalSum + A[2*node+1].prefix);
    // Calculate biggest suffix of A[node]
    A[node].suffix = max(A[2*node+1].suffix,A[2*node+1].totalSum + A[2*node].suffix);
    // Calculate A[node] biggest subsequence sum
    A[node].sum = max(A[2*node].sum, A[2*node+1].sum);
    A[node].sum = max(A[node].sum, A[2*node].suffix + A[2*node+1].prefix);
}
void query(int node, int st, int dr, int  a, int b)
{
    if(a<=st && dr<=b)
    {
        sol = max(sol, A[node].sum);
        sol = max(sol, suf + A[node].prefix);
        suf = max(A[node].suffix, suf + A[node].totalSum);
        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid)
        query(2*node,st,mid,a,b);
    if(b > mid)
        query(2*node+1,mid+1,dr,a,b);
    return;

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    build(1,1,n);
    for(int i = 1;i<=m;i++)
    {
        int x,y;
        cin >> x >> y;
        sol = suf = -1e18;
        query(1,1,n,x,y);
        cout << sol << '\n';

    }
    return 0;
}