#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

#define MAXN 100000

struct Node{
    long long max_sum_from_left, max_sum_from_right, max_sum, total_sum;
};

int n;
int v[MAXN];

Node aint[4 * MAXN];

int intervals[MAXN];
int no_intervals;

inline int leftChild(int index){
    return index * 2 + 1;
}
inline int rightChild(int index){
    return index * 2 + 2;
}

void build(int index, int nleft, int nright){
    if(nleft == nright){
        aint[index].max_sum_from_left = aint[index].max_sum_from_right = aint[index].max_sum = aint[index].total_sum = v[nleft];
        return;
    }

    int mid = (nleft + nright) / 2;

    build(leftChild(index), nleft, mid);
    build(rightChild(index), mid + 1, nright);

    aint[index].total_sum = aint[leftChild(index)].total_sum + aint[rightChild(index)].total_sum;

    aint[index].max_sum_from_left = max(aint[leftChild(index)].max_sum_from_left, 
                                        aint[leftChild(index)].total_sum + aint[rightChild(index)].max_sum_from_left);

    aint[index].max_sum_from_right = max(aint[rightChild(index)].max_sum_from_right, 
                                        aint[rightChild(index)].total_sum + aint[leftChild(index)].max_sum_from_right);

    aint[index].max_sum = max(max(aint[leftChild(index)].max_sum, aint[rightChild(index)].max_sum), 
                            aint[leftChild(index)].max_sum_from_right + aint[rightChild(index)].max_sum_from_left);

}

void calcIntervals(int node, int nleft, int nright, int qleft, int qright){
    if(qleft <= nleft && qright >= nright){
        intervals[no_intervals++] = node;
        return;
    }

    int mid = (nleft + nright) / 2;

    if(qleft <= mid){
        calcIntervals(leftChild(node), nleft, mid, qleft, qright);
    }

    if(qright > mid){
        calcIntervals(rightChild(node), mid + 1, nright, qleft, qright);
    }
}

long long query(int qleft, int qright){
    int i;
    long long sum, maxx;

    no_intervals = 0;
    calcIntervals(0, 0, n - 1, qleft, qright);

    maxx = aint[intervals[0]].max_sum;
    sum = aint[intervals[0]].max_sum_from_right;

    for(i = 1; i < no_intervals; i++){
        if(aint[intervals[i]].max_sum > maxx){
            maxx = aint[intervals[i]].max_sum;
        }

        if(sum + aint[intervals[i]].max_sum_from_left > maxx){
            maxx = sum + aint[intervals[i]].max_sum_from_left;
        }

        sum = max(aint[intervals[i]].max_sum_from_right,
                  sum + aint[intervals[i]].total_sum);

        if(sum > maxx){
            maxx = sum;
        }
    }

    return maxx;
}

int main() {
    int m, i, x, y;
    // n declarat global

    fin >> n >> m;

    for(i = 0; i < n; i++) {
        fin >> v[i];
    }

    build(0, 0, n - 1);

    for(i = 0; i < m; i++) {
        fin >> x >> y;
        fout << query(x - 1, y - 1) << '\n';
    }

    return 0;
}