#include <cstdio> //fopen, fscanf, fgetc, fread
#include <cctype> //isdigit
#include <algorithm> //max

#define NMAX 100000

#define BUF_SIZE 1 << 17

using namespace std;

FILE *fin = fopen("sequencequery.in", "r");
FILE *fout = fopen("sequencequery.out", "w");

char buf[BUF_SIZE]; //bufferul
int pos = BUF_SIZE;

inline char nextch(){
    if(pos == BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin); //mai intai vectorul, apoi dimensiunea, apoi cifra 1, apoi fisierul
        pos = 0; //fixam pozitia de la care incepem sa citim ca 0
    }

    return buf[pos++]; //returneaza buf[pos], dupa care creste pos
}

inline int read(){
    char ch = nextch();

    while( !isdigit(ch) && ch != '-' ){
        ch = nextch();
    }

    int semn = 1; //pozitiv
    if(ch == '-'){
        semn = -1;
        ch = nextch();
    }

    int nr = 0;
    while( isdigit(ch) ){
        nr = nr * 10 + ch - '0';
        ch = nextch();
    }

    return semn * nr;
}


struct element{
    long long maxIndSum; //max independent de unde se afla
    long long leftSum, rightSum;
    long long totSum;
};

int X, Y;
int v[NMAX + 1];
element tree[4 * NMAX + 1];


element rezultat(element A, element B, int dim1, int dim2){
    element rez;

    rez.maxIndSum = max(A.maxIndSum, B.maxIndSum);

    //if(A.rightSum > 0 && B.leftSum > 0){
        //cel din mijloc devine un candidat pt suma independenta
        rez.maxIndSum = max(rez.maxIndSum, A.rightSum + B.leftSum);

    rez.leftSum = max(A.leftSum, A.totSum + B.leftSum);
    rez.rightSum = max(B.rightSum, B.totSum + A.rightSum);

    rez.totSum = A.totSum + B.totSum;

    return rez;
}

void buildArbore(int node, int left, int right){
    if(left == right){
        tree[node].leftSum = v[left];
        tree[node].rightSum = v[left];

        tree[node].maxIndSum = v[left];
        tree[node].totSum = v[left];
        return;
    }

    int mid = left + (right - left) / 2;

    buildArbore(node * 2, left, mid);
    buildArbore(node * 2 + 1, mid + 1, right);

    tree[node] = rezultat(tree[node * 2], tree[node * 2 + 1], mid - left + 1, right - mid);
}

element query(int node, int left, int right){
    if(X <= left && right <= Y){
        return tree[node];
    }

    int mid = left + (right - left) / 2;

    element aux1, aux2;
    int OK1 = 0, OK2 = 0;
    if(X <= mid){
        //e relevant si fiul din stanga
        aux1 = query(node * 2, left, mid);
        OK1 = 1;
    }
    if(mid + 1 <= Y){
        //e relevant si fiul din dreapta
        aux2 = query(node * 2 + 1, mid + 1, right);
        OK2 = 1;
    }

    if(OK1 == 1 && OK2 == 1){
        return rezultat(aux1, aux2, mid - left + 1, right - mid); //daca le am pe ambele
    }
    else if(OK1 == 1){
        return aux1;
    }
    else {
        return aux2;
    }
}

int main()
{
    /*
    //testez functia rezultat();
    element A;
    A.leftSize = 3;
    A.rightSize = 3;
    A.maxIndSum = 30;
    A.leftSum = 30;
    A.rightSum = 30;

    element B;
    B.leftSize = 1;
    B.rightSize = 2;
    B.maxIndSum = 10;
    B.leftSum = 3;
    B.rightSum = 9;

    element AUB;
    AUB = rezultat(A, B, 3, 7);

    cout << AUB.leftSize << "\n" << AUB.rightSize << "\n" << AUB.maxIndSum << "\n" << AUB.leftSum << "\n" << AUB.rightSum;
    */


    int N, M;
    N = read();
    M = read();

    for(int i = 1; i <= N; i++){
        v[i] = read();
    }

    buildArbore(1, 1, N);


    for(int q = 1; q <= M; q++){
        X = read();
        Y = read();

        element aux = query(1, 1, N);
        fprintf(fout, "%d\n", aux.maxIndSum);
    }

    return 0;
}