#include <iostream>
#include <fstream>
#include <vector>
#define nl '\n'

using namespace std;

class InParser {
    private:
        std::vector<char> str;
        int ptr;
        std::ifstream fin;

    private:
        char getChar() {
            if (ptr == (int)str.size()) {
                fin.read(str.data(), (int)str.size());
                ptr = 0;
            }

            return str[ptr++];
        }

        template<class T>
        T getInt() {
            char chr;
            do {
                chr = getChar();
            } while (!isdigit(chr) && (chr != '-'));

            int sgn = +1;
            if (chr == '-') {
                sgn = -1;
                chr = getChar();
            }

            T num = 0;
            while (isdigit(chr)) {
                num = num * 10 + (chr - '0');
                chr = getChar();
            }

            return sgn * num;
        }

    public:
        InParser(const char *name) : str((int)1e5), ptr((int)str.size()), fin(name) { }
        ~InParser() { fin.close(); }

        template<class T>
        friend InParser &operator >> (InParser &in, T &num) {
            num = in.getInt<T>();
            return in;
        }
};

class OutParser {
    private:
        std::vector<char> str;
        int ptr;
        std::ofstream fout;

    private:
        void putChar(char chr) {
            if (ptr == (int)str.size()) {
                fout.write(str.data(), (int)str.size());
                ptr = 0;
            }

            str[ptr++] = chr;
        }

        template<class T>
        void putInt(T num) {
            if (num < 0) {
                putChar('-');
                num *= -1;
            }

            if (num > 9)
                putInt(num / 10);
            putChar(num % 10 + '0');
        }

    public:
        OutParser(const char *name) : str((int)1e5), ptr(0), fout(name) { }
        ~OutParser() { fout.write(str.data(), ptr); fout.close(); }

        template<class T>
        friend OutParser &operator << (OutParser &out, const T num) {
            out.putInt(num);
            return out;
        }

        friend OutParser &operator << (OutParser &out, const char chr) {
            out.putChar(chr);
            return out;
        }

        friend OutParser &operator << (OutParser &out, const char *str) {
            for (int i = 0; str[i]; i++)
                out.putChar(str[i]);
            return out;
        }
};

InParser fin("sequencequery.in");
OutParser fout("sequencequery.out");

const int NMAX = 1e5+5;

int n;
long long int suf, maxi;
struct info
{
    long long int sum, sumaMax, sufMax, prefMax;
} aint[4*NMAX];

void build(int node, int st, int dr)
{
    if (st == dr)
    {
        int x;
        fin >> x;
        aint[node] = {x, x, x, x};
    }
    else
    {
        int mid = (st+dr)/2;
        build(2*node, st, mid);
        build(2*node+1, mid+1, dr);
        aint[node].sum = aint[2*node].sum + aint[2*node+1].sum;
        aint[node].prefMax = max(aint[2*node].prefMax, aint[2*node].sum+aint[2*node+1].prefMax);
        aint[node].sufMax = max(aint[2*node+1].sufMax, aint[2*node+1].sum+aint[2*node].sufMax);
        aint[node].sumaMax = max(aint[2*node].sumaMax, aint[2*node+1].sumaMax);
        aint[node].sumaMax = max(aint[node].sumaMax, aint[2*node].sufMax+aint[2*node+1].prefMax);
    }
    return;
}

void query(int node, int st, int dr, int a, int b)
{
    if (a <= st && dr <= b)
    {
        maxi = max(maxi, aint[node].sumaMax);
        maxi = max(maxi, suf+aint[node].prefMax);
        suf = max(suf+aint[node].sum, aint[node].sufMax);
        return;
    }
    int mid = (st+dr)/2;
    if (a <= mid)
        query(2*node, st, mid, a, b);
    if (mid+1 <= b)
        query(2*node+1, mid+1, dr, a, b);
    return;
}

int main()
{
    int m;
    fin >> n >> m;
    build(1, 1, n);
    while (m--)
    {
        int a, b;
        fin >> a >> b;
        maxi = suf = -1e18;
        query(1, 1, n, a, b);
        fout << maxi << nl;
    }
    return 0;
}