#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];

    int 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]);
    }
}