#include <fstream>

using namespace std;

ifstream F("sequencequery.in");
ofstream G("sequencequery.out");

struct arbint{long long right, left, sum, best;} arb[400005];
int v[100005], x, y, n, m;
long long sum, ans;

long long Max(long long a, long long b){
    if(a>b) return a;
    return b;
}

void Build(int l, int r, int rad)
{
    if(l == r)
    {
        arb[rad].left = arb[rad].right = arb[rad].best = v[l];
        arb[rad].sum = v[l];
        return;
    }
    int mid = (l+r)/2;
    Build(l, mid, 2*rad);
    Build(mid+1, r, 2*rad+1);
    arb[rad].left = Max(arb[2*rad].left, arb[2*rad].sum + arb[2*rad+1].left);
    arb[rad].right = Max(arb[2*rad+1].right, arb[2*rad+1].sum + arb[2*rad].right);
    arb[rad].best = Max(Max(arb[2*rad].best, arb[2*rad+1].best), arb[2*rad].right+ arb[2*rad+1].left);
    arb[rad].sum = arb[2*rad].sum+arb[2*rad+1].sum;
}

void Query(int l, int r, int rad)
{
    if(x <= l && r <= y)
    {
        ans = Max(ans, Max(sum+arb[rad].left, arb[rad].best));
        sum = Max(arb[rad].right, arb[rad].sum+sum);
        return;
    }
    int mid = (l+r)/2;
    if(x<=mid) Query(l, mid, 2*rad);
    if(y > mid) Query(mid+1, r, 2*rad+1);
}

int main()
{
    F >> n >> m;
    for( int i = 1; i <= n; ++ i ) F >> v[i];
    Build(1, n, 1);
    while(m--)
    {
        F >> x >> y;
        ans = sum = -1LL<<62;
        Query(1, n, 1);
        G << ans << '\n';
    }
    return 0;
}