#include<stdio.h>
#include<algorithm>
using namespace std;
#define NMAX 100000
#define INF 1e18
struct AINT { long long sum,ssm,left,right; };
int n;
long long a[NMAX + 5];
AINT aint[3 * NMAX + 10];

long long max5 (long long a, long long b, long long c, long long d, long long e) {
    long long res = a;
    if(b > res) res = b;
    if(c > res) res = c;
    if(d > res) res = d;
    if(e > res) res = e;
    return res;
}

void build (int node, int left, int right) {
    if(left == right) {
        aint[node].sum = aint[node].ssm = aint[node].left = aint[node].right = a[left];
        return;
        }

    int mid = (left + right) / 2, leftSon = 2 * node, rightSon = 2 * node + 1;

    build(leftSon,left,mid);
    build(rightSon,mid + 1,right);

    aint[node].sum = aint[leftSon].sum + aint[rightSon].sum;
    aint[node].left = max(aint[leftSon].sum + aint[rightSon].left, aint[leftSon].left);
    aint[node].right = max(aint[rightSon].sum + aint[leftSon].right, aint[rightSon].right);
    aint[node].ssm = max5(aint[node].left,aint[node].right,aint[leftSon].ssm,aint[rightSon].ssm,aint[leftSon].right + aint[rightSon].left);
}

AINT query (int node, int left, int right, int a, int b) {
    if(a <= left && b >= right)
        return aint[node];

    int leftSon = 2 * node, rightSon = 2 * node + 1, mid = (left + right) / 2;
    AINT ans,LEFT = {-INF,-INF,-INF,-INF},RIGHT = {-INF,-INF,-INF,-INF};

    if(mid >= a)
        LEFT = query(leftSon,left,mid,a,b);
    if(mid < b)
        RIGHT = query(rightSon,mid + 1,right,a,b);

    if(LEFT.sum != -INF && RIGHT.sum != -INF) {
        ans.sum = LEFT.sum + RIGHT.sum;
        ans.left = max(LEFT.sum + RIGHT.left, LEFT.left);
        ans.right = max(RIGHT.sum + LEFT.right, RIGHT.right);
        ans.ssm = max5(ans.left,ans.right,LEFT.ssm,RIGHT.ssm,LEFT.right + RIGHT.left);
        return ans;
        }
    if(LEFT.sum == -INF)
        return RIGHT;
    return LEFT;
}

int main() {
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    int i,p2,m,x,y;
    scanf("%d%d",&n,&m);
    for(p2 = 1; p2 < n; p2 <<= 1);
    for(i = 1; i <= n; i++)
        scanf("%lld",&a[i]);
    build(1,1,p2);
    for(i = 1; i <= m; i++) {
        scanf("%d%d",&x,&y);
        printf("%d\n",query(1,1,p2,x,y).ssm);
        }
    return 0;
}