#include <stdio.h>     
#include <vector>     
using namespace std;     
     
typedef long long ll;     
struct un_nod     
{     
    ll s_st, s_dr, s_max, s_tot;     
};     
     
int n, pos, val, seq_start, seq_end;     
ll maxim, dreapta;     
vector<un_nod> arb;     
     
void solve();     
void update(int, int, int);     
void query(int, int, int);     
inline ll max(ll, ll);     
inline ll max(ll, ll, ll);     
     
int main()     
{     
    solve();     
    return 0;     
}     
     
void solve()     
{     
    int m;     
    FILE *fin = fopen("sequencequery.in", "r");     
    FILE *fout = fopen("sequencequery.out", "w");     
    fscanf(fin, "%d%d", &n, &m);     
    arb.resize(4 * n);     
     
    for (pos = 1; pos <= n; ++pos)     
    {     
        fscanf(fin, "%d", &val);     
        update(1, 1, n);     
    }     
         
    for (; m; --m)     
    {     
        fscanf(fin, "%d%d", &seq_start, &seq_end);     
        maxim = -100000;     
        dreapta = -100000;     
        query(1, 1, n);     
        fprintf(fout, "%lld\n", maxim);     
    }     
         
    fclose(fin);     
    fclose(fout);     
}     
     
void update(int nod, int st, int dr)     
{     
    if (st == dr)     
    {     
        arb[nod].s_st = arb[nod].s_dr = val;     
        arb[nod].s_max = arb[nod].s_tot = val;     
    }     
    else     
    {     
        int mid = (st + dr) / 2;     
        if (pos <= mid)     
        {     
            update(2 * nod, st, mid);     
        }     
        else     
        {     
            update(2 * nod + 1, mid + 1, dr);     
        }     
        arb[nod].s_tot = arb[2*nod].s_tot + arb[2*nod+1].s_tot;     
        arb[nod].s_st = max(arb[2*nod].s_tot + arb[2*nod+1].s_st, arb[2*nod].s_st);     
        arb[nod].s_dr = max(arb[2*nod+1].s_tot + arb[2*nod].s_dr, arb[2*nod+1].s_dr);     
        arb[nod].s_max = max(arb[2*nod].s_max, arb[2*nod+1].s_max, arb[2*nod].s_dr + arb[2*nod+1].s_st);     
    }     
}     
     
void query(int nod, int st, int dr)     
{     
    if (seq_start <= st && dr <= seq_end)     
    {     
//      un_nod p = arb[nod];     
        maxim = max(maxim, arb[nod].s_max, dreapta + arb[nod].s_st);     
        dreapta = max(arb[nod].s_dr, dreapta + arb[nod].s_tot);     
    }     
    else     
    {     
        int mid = (st + dr) / 2;     
        if (seq_start <= mid)     
        {     
            query(2 * nod, st, mid);     
        }     
        if (mid < seq_end)     
        {     
            query(2 * nod + 1, mid + 1, dr);     
        }     
    }     
}     
     
inline ll max(ll a, ll b)     
{     
    return ((a > b) ? a : b);     
}     
     
inline ll max(ll a, ll b, ll c)     
{     
    return ((a > b) ? ((a > c) ? a : c) : ((b > c) ? b : c));     
}