#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

/*******************************/
// INPUT / OUTPUT

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
/*******************************/
/// GLOBAL DECLARATIONS

int N, M;
bool primul;
struct Node
{
    long long sum, leftSum, rightSum, ssm;
} arb[4 * NMAX];
Node ans;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    f >> N >> M;
}
///-------------------------------------
void Update(const int &st, const int &dr, const int &idx, const int &pos, const long long &val)
{
    if (st == dr)
    {
        arb[idx].sum = val;
        arb[idx].leftSum = val;
        arb[idx].rightSum = val;
        arb[idx].ssm = val;
        return;
    }

    int mij = (st + dr) / 2;

    if (pos <= mij) Update(st, mij, 2 * idx, pos, val);
    else Update(mij + 1, dr, 2 * idx + 1, pos, val);

    arb[idx].sum = arb[2 * idx].sum + arb[2 * idx + 1].sum;
    arb[idx].ssm = max(arb[2 * idx].ssm, max(arb[2 * idx + 1].ssm, arb[2 * idx].rightSum + arb[2 * idx + 1].leftSum));
    arb[idx].leftSum = max(arb[2 * idx].leftSum, arb[2 * idx].sum + arb[2 * idx + 1].leftSum);
    arb[idx].rightSum = max(arb[2 * idx + 1].rightSum, arb[2 * idx + 1].sum + arb[2 * idx].rightSum);
}
///-------------------------------------
void Query(const int &arbSt, const int &arbDr, const int &st, const int &dr, const int &idx)
{
    if (dr < arbSt || st > arbDr)
    {
        return;
    }
    
    if (st <= arbSt && dr >= arbDr)
    {
        if (primul)
        {
            ans.ssm = arb[idx].ssm, ans.rightSum = arb[idx].rightSum;
            primul = false;
        }
        else
        {
            ans.ssm = max(ans.ssm, max(arb[idx].ssm, ans.rightSum + arb[idx].leftSum));
            ans.rightSum = max(arb[idx].rightSum, ans.rightSum + arb[idx].sum);
        }
        return;
    }

    int mij = (arbSt + arbDr) / 2;
    
    Query(arbSt, mij, st, dr, 2 * idx);
    Query(mij + 1, arbDr, st, dr, 2 * idx + 1);
    return;
}
///-------------------------------------
inline void Solution()
{
    long long num;
    for (int i = 1 ; i <= N ; ++ i)
    {
        f >> num;
        Update(1, N, 1, i, num);
    }

    int a, b;
    while (M --)
    {
        f >> a >> b;
        primul = true;
        Query(1, N, a, b, 1);
        g << ans.ssm << "\n";
    }
}
///-------------------------------------
int main()
{
    ReadInput();
    Solution();
    return 0;
}