#include <iostream>
#include <fstream>
#include <cmath>
#define nl '\n'
using namespace std;
ifstream f ( "sequencequery.in" );
ofstream g ( "sequencequery.out" );
const int NMAX = 100001, SQRT = sqrt ( NMAX ) + 10;
const long long INF = 1e9;
int a[NMAX];
long long sum[NMAX], mnsecv[SQRT], mxsecv[SQRT], best[SQRT];
int main()
{
    int N, M, K;
    f >> N >> M;
    K = sqrt ( N );
    int nrsecv = 1;

    for ( int i = 1; i <= N; i++ )
    {
        f >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    int nrtotsecv = ( N - 1 ) / K + 1;

    for ( int i = 0; i < nrtotsecv; i++ )
    {
        int in = i * K + 1, sf = in + K;
        int mn = INF;
        mnsecv[i + 1] = sum[in - 1];

        for ( int j = in; j < sf; j++ )
        {
            mnsecv[i + 1] = min ( mnsecv[i + 1], sum[j] );
            mxsecv[i + 1] = max ( mxsecv[i + 1], sum[j] );
            best[i + 1] = max ( best[i + 1], sum[j] - mnsecv[i + 1] );
        }
    }

    int x, y;

    while ( M-- )
    {
        f >> x >> y;

        if ( y - x <= K )
        {
            long long ans = sum[y] - sum[x - 1], mx = INF, mn = sum[x - 1];

            for ( int i = x; i <= y; i++ )
            {
                ans = max ( ans, sum[i] - mn );
                mn = min ( mn, sum[i] );
            }

            g << ans << nl;
            continue;
        }

        long long  sfsecvx = ( ( x - 1 ) / K + 1 ) * K, mn1 = sum[x - 1], bst = -INF;

        for ( int i = x; i <= sfsecvx; i++ )
        {
            bst = max ( bst, sum[i] - mn1 );
            mn1 = min ( mn1, sum[i] );
        }

        int insecvy = ( y - 1 ) / K * K + 1;
        long long mx1 = sum[insecvy];
        long long mn = INF, mn3 = sum[insecvy - 1];

        for ( int i = insecvy; i <= y; i++ )
        {
            mx1 = max ( mx1, sum[i] );
            bst = max ( bst, mx1 - mn3 );
            mn3 = min ( mn3, sum[i] );
        }

        mn = mn1;
        int sx = ( x - 1 ) / K + 1;
        int sy = ( y - 1 ) / K + 1;

        for ( int i = sx + 1; i < sy; i++ )
        {
            bst = max ( bst, mxsecv[i] - mn );
            bst = max ( bst, best[i] );
            mn = min ( mn, mnsecv[i] );
        }

        bst = max ( bst, mx1 - mn );
        g << bst << nl;
    }

    return 0;
}