#include <fstream>
#include <iostream>
using namespace std;

const int N = 1 << 17;

struct Nod{
    long long st, dr, tot, best;

    Nod() : st(0), dr(0), tot(0), best(0) {};
    Nod(int val) : st(val), dr(val), tot(val), best(val) {};
    Nod(long long st, long long dr, long long tot, long long best) : st(st), dr(dr), tot(tot), best(best) {};

    inline static int max(int a, int b){
        return a > b ? a : b;
    }

    inline static int max(int a, int b, int c){
        return max( a, max(b, c) );
    }

    inline Nod operator+(const Nod& N) const {
        return Nod( max(st, tot + N.st), max(dr + N.tot, N.dr), tot + N.tot, max(best, N.best, dr + N.st) );
    }
};

template<class Type = int>
class Aint{
    Type aint[2 * N];

public:
    void update(int poz, Type val){
        aint[ poz += N - 1 ] = val;
        while (poz >>= 1)
            aint[poz] = aint[poz << 1] + aint[1 + (poz << 1)];
    }

    Type query(int x, int y){
        if (x == y) return aint[x + N - 1];

        Type ansX = aint[x += N - 1], ansY = aint[y += N - 1];

        int stopX = x >> (31 - __builtin_clz(x ^ y) );
        int stopY = y >> (31 - __builtin_clz(x ^ y) );

        while ( stopX < ( x >>= __builtin_ctz(~x) ) )
            ansX = ansX + aint[x ^= 1];
        while ( stopY < ( y >>= __builtin_ctz(y) ) )
            ansY = aint[y ^= 1] + ansY;

        return ansX + ansY;
    }
};

Aint<Nod> A;

int main(){
    int n, nrQ, x, y;
    ifstream in("sequencequery.in");

    in >> n >> nrQ;
    for (int i = 1 ; i <= n ; i++){
        in >> x;
        A.update( i, Nod(x) );
    }

    ofstream out("sequencequery.out");
    while (nrQ--){
        in >> x >> y;
        out << A.query(x, y).best << '\n';
    }

    out.close();
    in.close();

    return 0;
}