# include <cstdio>
# define MAXN 100001
# define INF -2000000000

using namespace std;
int a[MAXN],i,j,n,bestsum,sum,x,y,m;

int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    scanf("%d %d\n", &n, &m);
    for(i=1; i<=n; ++i)
        scanf("%d ", &a[i]);
    for(i=1; i<=m; ++i)
    {
        scanf("%d %d", &x, &y);
        sum=0;
        bestsum=INF;
        for(j=x; j<=y; ++j)
        {
            if(sum<0) sum=a[j];
            else sum+=a[j];
            if(sum>bestsum) bestsum=sum;
        }
        printf("%d\n", bestsum);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}