#include <fstream>
#include <stdio.h>
#include <iostream>
#define N_MAX 100002

using namespace std;

int arr[N_MAX];
int n, m;

struct nodeAint {
    int sum, prefixMax, sufixMax, secvMax;
};
nodeAint aint[4*N_MAX];

nodeAint updateNote (nodeAint left, nodeAint right){
    nodeAint currentNode;

    currentNode.sum = left.sum + right.sum;
    currentNode.secvMax = max(max(left.secvMax, right.secvMax), left.sufixMax + right.prefixMax);
    currentNode.prefixMax = max(left.prefixMax, left.sum + right.prefixMax);
    currentNode.sufixMax = max(right.sufixMax, right.sum + left.sufixMax);

    return currentNode;
}

void build (int node, int left, int right){
    if (left == right){
        aint[node].prefixMax = arr[left];
        aint[node].sufixMax = arr[left];
        aint[node].sum = arr[left];
        aint[node].secvMax = arr[left];
    }
    else{
        int middle = (left+right) / 2;

        build (node*2, left, middle);
        build (node*2+1, middle + 1, right);

        aint[node] = updateNote (aint[2*node], aint[2*node+1]);
    }
}

nodeAint query (int node, int left, int right, int x, int y){
    if (left >= x && right <= y) 
        return aint[node]; // tot intervalul respectiv se afla in query
    else{
        int middle = (left+right) / 2;

        if (y <= middle)
            return query(node*2, left, middle, x, y);
        if (middle < x) // se afla numai un interval
            return query(node*2+1, middle + 1, right, x, y);
        
        nodeAint leftNode = query(node*2, left, middle, x, y);
        nodeAint rightNode = query(node*2+1, middle + 1, right, x, y);
 
        return updateNote(leftNode, rightNode);
    }
}

int main (){
    FILE *in, *out;
    in = fopen ("sequencequery.in", "r");
    out = fopen ("sequencequery.out", "w");

    fscanf (in, "%d%d", &n, &m);
    for (int i=1; i<=n; ++i)
        fscanf(in, "%d", &arr[i]);

    build (1, 1, n);

    int x, y, rez;
    for (int i=1; i<=m; ++i){
        fscanf(in, "%d%d", &x, &y); // interval
        rez = query(1, 1, n, x, y).secvMax;
        fprintf (out, "%d \n", rez);
    }
    return 0;
}