#include <bits/stdc++.h>
using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");

const int NMAX =  100005;

struct AINT
{
    long long left , right , SSM , ST;
};
AINT aint[4 * NMAX];

/**

  aint[node] . left - > subsecventa de suma maxima ce incepe cu capatul stang a intervalului
  aint[nod] . right -> subsecventa de suma maxima ce se termina in capatul drept a intervalului
  aint[node] . ST -> suma totatala a intervalului
  aint[node] . SSM - > subsecventa de suma maxima a intervalului
*/

int n , Q;

void UPDATE(int node , int left , int right , int a , int b)
{
    if(left == right)
    {
        aint[node] . left = aint[node] . right = aint[node] . SSM  = aint[node] . ST = b;
        return;
    }
    int middle = (left + right) / 2;
    if(a <= middle)
        UPDATE(2 * node , left , middle , a , b);
    else UPDATE(2 * node + 1 , middle + 1 , right , a , b);
    aint[node] . ST = aint[2 * node] . ST + aint[2 * node + 1] . ST;
    aint[node] . right = max(aint[2 * node + 1] . right , aint[2 * node] . right + aint[2 * node + 1] . ST);
    aint[node] . left = max(aint[2 * node] . left , aint[2 * node] . ST + aint[2 * node + 1] . left);
    /// subsecventa de suma maxima se afla in totalite in intervalul primului fiu sau se afla in totalitate in intervalul celui de-al doilea fiu
    /// sau se afla partial in intervalul primului fiu si partial in intervalul celui de-al doilea
    aint[node] . SSM = max({aint[2 * node] . SSM , aint[2 * node + 1] . SSM , aint[2 * node] . right + aint[2 * node + 1] . left});
}

AINT QUERY(int node , int left , int right , int X , int Y)
{
    if(left == X && right == Y)
        return aint[node];
    int middle = (left + right) / 2;
    if(Y <= middle)
        return QUERY(2 * node , left , middle , X , Y);
    else if(X > middle)
        return QUERY(2 * node + 1 , middle + 1 , right , X , Y);
    else
    {
        AINT P , P1 , P2;
        P = QUERY(2 * node , left , middle , X , middle);
        P1 = QUERY(2 * node + 1 , middle + 1 , right , middle + 1 , Y);
        P2 . ST = P . ST + P1 . ST;
        P2 . left = max(P . left , P1 . left + P . ST);
        P2 . right = max(P1 . right , P . right + P1 . ST);
        P2 . SSM = max({P . SSM , P1 . SSM , P . right + P1 . left});
        return P2;
    }
}
int main()
{
    AINT w;
    int x , y;
    fin >> n >> Q;
    for(int i = 1 ; i <= n ; i++)
    {
        fin >> x;
        UPDATE(1 , 1 , n , i , x);
    }
    while(Q -- )
    {
        fin >> x >> y;
        w = QUERY(1 , 1 , n , x , y );
        fout << w . SSM << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}