#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));  
}