#include <cstdio>
#include <ctype.h>
#define BUF_SIZE (1<<17)
#define MAXN 100000
#define INF -100001
 
char buf[BUF_SIZE], buf2[BUF_SIZE];
int n, m, pos = BUF_SIZE, pos2, l1, l2;
long long s, prefix[(1<<18)], sufix[(1<<18)], suma[(1<<18)], v[MAXN+1], maxs[(1<<18)];
 
FILE *fin, *fout;
 
inline char getChar();
inline int getInt();
inline void putch(char);
inline void scrie(long long);
 
inline long long maxim(long long a, long long b){
    return (a>b) ? a : b;
}
 
inline void dfs(int st, int dr, int nod)
{
    if(st == dr)
    {
        prefix[nod] = v[st];
        sufix[nod] = v[st];
        suma[nod] = v[st];
        maxs[nod] = v[st];
        return;
    }
    int m = (st+dr)/2;
    dfs(st, m, nod*2);
    dfs(m+1, dr, nod*2+1);
 
    prefix[nod] = maxim(suma[nod*2] + prefix[nod*2+1], prefix[nod*2]);
    sufix[nod] = maxim(suma[nod*2+1] + sufix[nod*2], sufix[nod*2+1]);
    suma[nod] = suma[nod*2] + suma[nod*2+1];
    maxs[nod] = maxim(sufix[nod*2] + prefix[nod*2+1], maxim(maxs[nod*2+1], maxs[nod*2]));
}
 
long long sufix_max(int st, int dr, int nod, int a, int b)
{
    if(a <=st && dr <= b)
        return sufix[nod];
 
    int m=(st+dr)/2, aux1, aux2;
 
    if(a <= m)
    {
        aux1 = sufix_max(st, m, nod*2, a, b);
        aux2 = sufix_max(m+1, dr, nod*2+1, a, b);
 
        return maxim(suma[nod*2+1] + aux1, aux2);
    }
    else return sufix_max(m+1, dr, nod*2+1, a, b);
}
 
long long prefix_max(int st, int dr, int nod, int a, int b)
{
    if(a <=st && dr <= b)
        return prefix[nod];
 
    int m=(st+dr)/2, aux1, aux2;
 
    if(b > m)
    {
        aux1 = prefix_max(m+1, dr, nod*2+1, a, b);
        aux2 = prefix_max(st, m, nod*2, a, b);
 
        return maxim(suma[nod*2] + aux1, aux2);
    }
    else return prefix_max(st, m, nod*2, a, b);
}
 
long long query(int st, int dr, int nod)
{
    if(l1 <= st && dr <= l2)
        return maxs[nod];
 
    long long sufix=0, prefix=0, m, maxst=INF, maxdr=INF;
 
    m = (st+dr)/2;
    if(l2 <= m) return query(st, m, nod*2);
    if(l1 > m) return query(m+1, dr, nod*2+1);
 
    sufix = sufix_max(st, m, nod*2, l1, m);
    prefix = prefix_max(m+1, dr, nod*2+1, m+1, l2);
    maxst = query(st, m, nod*2);
    maxdr = query(m+1, dr, nod*2+1);
 
    return maxim(sufix + prefix, maxim(maxst, maxdr));
}
 
int main()
{
    fin = fopen("sequencequery.in", "r");
    fout = fopen("sequencequery.out", "w");
 
    int n, m, i;
 
    n=getInt(); m=getInt();
    for(i=1;i<=n;++i)
        v[i] = getInt();
 
    dfs(1, n, 1);
 
    for(i=1;i<=m;++i)
    {
        s=INF;
        l1=getInt(); l2=getInt();
        s=query(1, n, 1);
        scrie(s);
        putch('\n');
    }
    fwrite(buf2, 1, pos2, fout);
 
    fclose(fin);
    fclose(fout);
 
    return 0;
}
 
inline char getChar()
{
    if(pos == BUF_SIZE) pos = 0, fread(buf, 1, BUF_SIZE, fin);
    return buf[pos++];
}
 
inline int getInt()
{
    int nr=0, sg=1;
    char c;
 
    c=getChar();
    while(!isdigit(c) && c != '-') c=getChar();
    if(c == '-') sg = -1, c=getChar();
 
    while(isdigit(c))
    {
        nr = nr*10 + c-'0';
        c=getChar();
    }
 
    return nr*sg;
}
 
inline void putch(char c)
{
    buf2[pos2++] = c;
    if(pos2 == BUF_SIZE) pos2=0, fwrite(buf2, 1, BUF_SIZE, fout);
}
inline void scrie(long long nr)
{
    char s[20];
    int k=0, sg=0;
    if(nr < 0)
        sg=1, nr*=-1;
    do
    {
        s[k++] = nr%10 + '0';
        nr/=10;
    }while(nr);
 
    if(sg) s[k++] = '-';
 
    while(k)
    {
        --k;
        putch(s[k]);
    }
}