#include <fstream>
#define nmax 100000
using namespace std;
ifstream is ("sequencequery.in");
ofstream os ("sequencequery.out");

#define mid (left+right)/2

struct Arbore {
    long long left;
    long long right;
    long long sum;
    long long ans;
} Arb[4*nmax];

long long ANSW, RIGHT, INF;
int N, M, x, y, L, R;

void Read();
void Build(int,int,int);
void Query(int,int,int);

int main()
{
    INF = -0x3f3f3f3f;
    Read();
    for(int i = 1; i <= M; ++i)
    {
        ANSW = INF;
        RIGHT = 0;
        is >> L >> R;
        Query(1, 1, N);
        os << ANSW << "\n";
    }
    is.close();
    os.close();
    return 0;
}
void Read()
{
    is >> N >> M;
    for(int i = 1; i <= N; ++i)
    {
        is >> x;
        y = i;
        Build(1, 1, N);
    }
}
void Build(int node, int left, int right)
{
    if(left == right)
    {
        Arb[node].left = Arb[node].right = Arb[node].ans = Arb[node].sum = x;
        return;
    }

    if(y <= mid) Build(2*node, left, mid);
    else Build(2*node+1, mid+1, right);

    Arb[node].left = max(Arb[2*node].left, Arb[2*node].sum + Arb[2*node+1].left);
    Arb[node].right = max(Arb[2*node+1].right, Arb[2*node+1].sum + Arb[2*node].right);
    Arb[node].ans = Arb[2*node].right + Arb[2*node+1].left;
    Arb[node].ans = max(Arb[node].ans, max(Arb[2*node].ans, Arb[2*node+1].ans));
    Arb[node].sum = Arb[2*node].sum + Arb[2*node+1].sum;
}
void Query(int node, int left, int right)
{
    if(left >= L && right <= R)
    {
        ANSW = max(ANSW, max(RIGHT + Arb[node].left, Arb[node].ans));
        RIGHT = max(RIGHT + Arb[node].sum, Arb[node].right);

        return;
    }

    if(L <= mid) Query(2*node, left, mid);
    if(mid < R) Query(2*node+1, mid+1, right);
}