#include <stdio.h>
#include <iostream>

#define NMAX 100005

using namespace std;

FILE *fin = fopen("sequencequery.in", "r");
FILE *fout = fopen("sequencequery.out", "w");

struct interval {long long bun; long long inc; long long sf;} v[4*NMAX];

int n,q,x,i,a,b,A[NMAX];
long long sumst,sum[NMAX],ans;

void update(int nod, int left, int right)
{
    if(left == right)
    {
        v[nod].bun = v[nod].inc = v[nod].sf = A[i];
        return;
    }

    int mid = (left+right) /2;
    if(i <= mid)
        update(2*nod, left, mid);
    else
        update(2*nod+1, mid+1, right);

    v[nod].bun = max(v[2*nod].bun, v[2*nod+1].bun);
    v[nod].bun = max(v[nod].bun, v[2*nod].sf+v[2*nod+1].inc);
    v[nod].inc = max(v[2*nod].inc, sum[mid]-sum[left-1] + v[2*nod+1].inc);
    v[nod].sf = max(v[2*nod+1].sf, v[2*nod].sf + sum[right]-sum[mid]);
}

void query(int nod, int left, int right)
{
    if(a<=left and right<=b)
    {
        ans = max(v[nod].bun, sumst+v[nod].inc);
        sumst = max(sumst + sum[right]-sum[left-1], v[nod].sf);
        return;
    }

    int mid = (left+right) /2;
    if(a <= mid)
        query(2*nod, left, mid);
    if(b > mid)
        query(2*nod+1, mid+1, right);
}

int main()
{
    fscanf(fin, "%d%d", &n,&q);
    for(i=1; i<=n; ++i)
    {
        fscanf(fin, "%d", &A[i]);
        sum[i] = sum[i-1] + 1LL*A[i];
    }
    for(i=1; i<=n; ++i)
        update(1, 1, n);

    while(q)
    {
        fscanf(fin, "%d%d", &a,&b);
        sumst = -1e18;
        ans = -1e18;
        query(1, 1, n);
        fprintf(fout, "%lld\n", ans);

        --q;
    }

    fclose(fin);
    fclose(fout);
    return 0;
}