#include <bits/stdc++.h>

#define inf     1000000005
#define MAXN    100005
#define _Left   2*Index
#define _Right  2*Index+1
#define _Middle (Left+Right)/2

int N, M;
int V[MAXN];

int MTree[4*MAXN], LTree[4*MAXN], RTree[4*MAXN], STree[4*MAXN];

int p = 1;
void BuildTree(int Left = 1, int Right = N, int Index = 1) {
    if (Left == Right) {
        MTree[Index] = LTree[Index] = RTree[Index] = STree[Index] = V[p++];
        return;
    }

    BuildTree(Left, _Middle, _Left);
    BuildTree(_Middle+1, Right, _Right);

    STree[Index] = STree[_Left] + STree[_Right];
    LTree[Index] = std::max(STree[_Left] + LTree[_Right], LTree[_Left]);
    RTree[Index] = std::max(STree[_Right] + RTree[_Left], RTree[_Right]);
    MTree[Index] = std::max(std::max(MTree[_Left], MTree[_Right]), RTree[_Left] + LTree[_Right]);
}

int SAux, Max;
void Query(int A, int B, int Left = 1, int Right = N, int Index = 1) {
    if (A <= Left && Right <= B) {
        Max = std::max(Max, std::max(SAux + LTree[Index], MTree[Index]));
        SAux = std::max(SAux + STree[Index], RTree[Index]);
        return;
    }

    if (A <= _Middle)
        Query(A, B, Left, _Middle, _Left);
    if (_Middle+1 <= B)
        Query(A, B, _Middle+1, Right, _Right);
}

std::ifstream In("sequencequery.in");
std::ofstream Out("sequencequery.out");

void Citire() {
    In >> N >> M;

    for (int i=1; i<=N; ++i)
        In >> V[i];
}

void Rezolvare() {
    BuildTree();

    for (int i=0, x, y; i<M; ++i)
        In >> x >> y,
        Max = -inf, SAux = -inf,
        Query(x, y),
        Out << Max << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}