#include <iostream>
#include <stdio.h>
using namespace std;
FILE *f,*g;
struct arbore
{
    long long st, dr, ssm, all;
}arb[400002];
int v[100002];
int n,m,a,b;
long long s,sol;
void read()
{
    fscanf(f,"%d %d",&n,&m);
    for(int i=1; i<=n; i++)
        fscanf(f,"%d ",&v[i]);
}
long long maxim(long long a, long long b)
{
    return a>b ? a:b;
}
void update(int node, int st, int dr)
{
    if(st==dr)
    {
        arb[node].all=arb[node].dr=arb[node].ssm=arb[node].st=v[st];
        return;
    }
    int mij=(st+dr)/2;
    update(2*node,st, mij);
    update(2*node+1,mij+1, dr);
    arb[node].all=arb[2*node].all+arb[2*node+1].all;
    arb[node].dr=maxim(arb[2*node+1].dr, arb[2*node+1].all+arb[2*node].dr);
    arb[node].st=maxim(arb[2*node].st, arb[2*node].all+arb[2*node+1].st);
    arb[node].ssm=maxim(arb[2*node].dr+arb[2*node+1].st, maxim(arb[2*node].ssm,arb[2*node+1].ssm));
}
void querry(int node, int st, int dr)
{
    if(a<=st && b>=dr)
    {
        if(s<0)
            s=0;
        sol=maxim(sol, maxim(s+arb[node].st, arb[node].ssm));
        s=maxim(s+arb[node].all, arb[node].dr);
    }
    else
    {
        int mij=(st+dr)/2;
        if(a<=mij)
            querry(2*node, st, mij);
        if(b>mij)
            querry(2*node+1, mij+1, dr);
    }
}
void solve()
{
    update(1,1,n);
    for(int i=1; i<=m; i++)
    {
        fscanf(f,"%d %d",&a,&b);
        s=sol=-999999999;
        querry(1,1,n);
        fprintf(g,"%lld\n",sol);
    }
}
int main()
{
    f=fopen("sequencequery.in","r");
    g=fopen("sequencequery.out","w");
    read();
    solve();
  //  write();
    fclose(f);
    fclose(g);
    return 0;
}