#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define INF 21400000000
#define MaxT 265000
#define MaxN 100001
#define MAX 131072
using namespace std;
 
FILE *IN,*OUT;
struct _Tree
{
    long long Sum,Left,Right,Max;
}T[MaxT];
int N,M,pos=0,v[MaxN],Start,End,out=0,sign;
long long Previous,Ans;
char f[MAX],Out[MAX],str[20];
inline void Write_Ch(char ch)
{
    Out[out++]=ch;
    if(out==MAX)
        fwrite(Out,MAX,1,OUT),out=0;
}
inline void Write_Int(long long nr)
{
    int x=0;
    if(nr<0)Write_Ch('-'),nr=-nr;
    do
    {
        str[x++]=nr%10+'0';
        nr/=10;
    }
    while(nr);
    while(x>0)
        Write_Ch(str[--x]);
}
inline long long max2(long long a,long long b)
{
    if (a>b) return a;
    else return b;
}
inline void Read(int &nr)
{
    sign=0;
    nr=0;
    while(f[pos]<'0'||f[pos]>'9')
    {
        if(f[pos]=='-')sign=1;
        pos++;
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
    while(f[pos]>='0'&&f[pos]<='9')
    {
        nr=10*nr+f[pos++]-'0';
        if(pos==MAX)
            fread(f,MAX,1,IN),pos=0;
    }
    if(sign)nr=-nr;
}
void DFS(int node,int start,int end)
{
    if(start==end)
    {
        T[node].Left=T[node].Right=T[node].Max=T[node].Sum=v[start];
        return;
    }
    DFS(node*2,start,(start+end)>>1);
    DFS(node*2+1,((start+end)>>1)+1,end);
    T[node].Sum=T[node*2].Sum+T[node*2+1].Sum;
    T[node].Left=max2(T[2*node].Sum+T[2*node+1].Left,T[2*node].Left);
    T[node].Right=max2(T[2*node+1].Sum+T[2*node].Right,T[2*node+1].Right);
    T[node].Max=max2(max2(T[2*node].Max,T[2*node+1].Max),T[2*node].Right+T[2*node+1].Left);
}
void Query(int node,int start,int end)
{
    if(start>=Start&&end<=End)
    {
        if(Previous<0)Previous=0;
        Ans=max2(Ans,max2(Previous+T[node].Left,T[node].Max));
        Previous=max(Previous+T[node].Sum,T[node].Right);
    }
    else
    {
        int mid=(start+end)>>1;
        if (Start<=mid)
            Query(node*2,start,mid);
        if(End>mid) Query(node*2+1,mid+1,end);
    }
}
int main()
{
    IN=fopen("sequencequery.in","r");
    OUT=fopen("sequencequery.out","w");
    fread(f,1,MAX,IN);
    Read(N);
    Read(M);
    for(int i=1;i<=N;i++)
        Read(v[i]);
    DFS(1,1,N);
    for(int i=1;i<=M;i++)
    {
        Previous=0;
        Ans=-INF;
        Read(Start),Read(End);
        Query(1,1,N);
        Write_Int(Ans);
        Write_Ch('\n');
    }
    if(out>0)fwrite(Out,1,out,OUT);
    return 0;
}