#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 1e5 + 1;
long long INF = 1e5 + 5; /// Max val is 100.000
int N, M;

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	freopen((name + ".in").c_str(), "r", stdin);
	freopen((name + ".out").c_str(), "w", stdout);
}

struct SegmentTree
{
    struct Node
    {
        long long maxi, leftMaxi, rightMaxi;
        long long sum;
    };

    Node A[4 * N_MAX];
    int pos, value; // local variables for Update
    int bg, ed;     // local variables for Query

    inline long long Maxi(long long a, long long b)
    {
        return a > b ? a : b;
    }

    Node MiniR(Node& a, Node& b) // Min with both values as referances
    {
        Node temp;

        temp.sum = a.sum + b.sum;
        temp.leftMaxi = Maxi(a.leftMaxi, a.sum + b.leftMaxi);
        temp.rightMaxi = Maxi(b.rightMaxi, b.sum + a.rightMaxi);
        temp.maxi = max({temp.leftMaxi, temp.rightMaxi, a.maxi, b.maxi});

        return temp;
    }

    Node Mini(Node& a, Node b) // Min with only the first value as referance
    {
        Node temp;

        temp.sum = a.sum + b.sum;
        temp.leftMaxi = Maxi(a.leftMaxi, a.sum + b.leftMaxi);
        temp.rightMaxi = Maxi(b.rightMaxi, b.sum + a.rightMaxi);
        temp.maxi = max({temp.leftMaxi, temp.rightMaxi, a.maxi, b.maxi});

        return temp;
    }

    void Build(int node, int L, int R)
    {
        if(L == R)
        {
            cin >> A[node].sum;
            A[node].maxi = A[node].leftMaxi = A[node].rightMaxi = A[node].sum;
            return;
        }

        int m = (L + R) >> 1;
        Build(node << 1, L, m);
        Build((node << 1) + 1, m + 1, R);

        A[node] = MiniR(A[node << 1], A[(node << 1) + 1]);
    }

    void Update(int pos, int value)
    {
        this->pos = pos;
        this->value = value;
        Update(1, 1, N);
    }

    void Update(int node, int L, int R)
    {
        if(L == R)
        {
            A[node].sum = value;
            A[node].maxi = A[node].leftMaxi = A[node].rightMaxi = A[node].sum;
            return;
        }

        int m = (L + R) >> 1;

        if(pos <= m)
            Update(node << 1, L, m);
        if(m < pos)
            Update((node << 1) + 1, m + 1, R);

        A[node] = MiniR(A[node << 1], A[(node << 1) + 1]);
    }

    Node Query(int bg, int ed)
    {
        this->bg = bg;
        this->ed = ed;

        return Query(1, 1, N);
    }

    Node Query(int node, int L, int R)
    {
        if(bg <= L && R <= ed)
            return A[node];

        int m = (L + R) >> 1;

        Node temp = Node{-INF, -INF, -INF, 0};
        if(bg <= m)
            temp = Mini(temp, Query(node << 1, L, m));
        if(m < ed)
            temp = Mini(temp, Query((node << 1) + 1, m + 1, R));

        return temp;
    }

} tree;

void AnswerQueries()
{
    int x, y;
    while(M--)
    {
        cin >> x >> y;
        cout << tree.Query(x, y).maxi << '\n';
    }
}

int main()
{
    SetInput("sequencequery");
    cin >> N >> M;
    tree.Build(1, 1, N);
    AnswerQueries();

    return 0;
}