#include <fstream>
#include <iostream>
#include <limits>

#define MAXN 100001
#define LOG2MAXN 18

using namespace std;

typedef long long int64;

struct IntervalData
{
    IntervalData() /*:
        maxSubSeq(numeric_limits<int64>::min()),
        maxSum(numeric_limits<int>::min()),
        minSum(numeric_limits<int>::max())*/
    {}
    
    IntervalData(const int64 maxSS,
                 const int64 maxS,
                 const int64 minS) :
        maxSubSeq(maxSS),
        maxSum(maxS),
        minSum(minS)
    {}

    int64 maxSubSeq;
    int64 maxSum;
    int64 minSum;
};

static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

IntervalData LookupTable[MAXN][LOG2MAXN];

void BuildLookupTable(const int n)
{
    for (int i=1; (1<<i) <= n; ++i)
    {
        for (int j=1; j<=n-(1<<i)+1; ++j)
        {
            const int prevIndex = i-1;
            LookupTable[j][i].minSum = min(LookupTable[j][prevIndex].minSum, LookupTable[j+(1<<(prevIndex))][prevIndex].minSum);
            LookupTable[j][i].maxSum = max(LookupTable[j][prevIndex].maxSum, LookupTable[j+(1<<(prevIndex))][prevIndex].maxSum);
            LookupTable[j][i].maxSubSeq = max(max(LookupTable[j][prevIndex].maxSubSeq, LookupTable[j+(1<<(prevIndex))][prevIndex].maxSubSeq),
                                              LookupTable[j+(1<<(prevIndex))][prevIndex].maxSum - LookupTable[j][prevIndex].minSum);
        }
    }
}

int64 Query(const int l, const int r)
{
    unsigned int n = r-l+1;
    int index = l;
    int64 curMin = LookupTable[l-1][0].minSum;
    int64 maxSubSeq = numeric_limits<int64>::min();

    while (n)
    {
        const unsigned int lsb = (n & -n);
        const int pos = MultiplyDeBruijnBitPosition[((unsigned int)(lsb * 0x077CB531U)) >> 27];
        
        //cout << pos << "\n";
        
        maxSubSeq = max(max(maxSubSeq, LookupTable[index][pos].maxSubSeq), LookupTable[index][pos].maxSum - curMin);
        curMin = min(curMin, LookupTable[index][pos].minSum);

        n -= lsb;
        index += lsb;
    }
    //cout << "\n";
    
    return maxSubSeq;
}

int main()
{
    int n,m;
    fstream fin("sequencequery.in", fstream::in);
    fstream fout("sequencequery.out", fstream::out);
    
    fin >> n >> m;
    //cout << n << " " << m << "\n";
    
    int64 sum=0;

    LookupTable[0][0] = IntervalData(0,0,0);
    for (int i=1; i<=n; ++i)
    {
        int x;
        fin >> x;
        sum += x;
        
        LookupTable[i][0] = IntervalData(x,sum,sum);
        
        //cout << sum << " ";
        
    }
    //cout << "\n\n";
    
    BuildLookupTable(n);
    
    /*for (int i=0; i<=n; ++i)
    {
        for (int j=0; j<=7; ++j)
        {
            cout << "(" << LookupTable[i][j].maxSubSeq << ", " << LookupTable[i][j].minSum << ", " << LookupTable[i][j].maxSum << ")  ";
        }
        cout << "\n";
    }
    
    cout << Query(1,5) << "\n";
    cout << Query(4,8) << "\n";
    cout << Query(6,6) << "\n";*/
    
    for (int i=0; i<m; ++i)
    {
        int a, b;
        fin >> a >> b;
        
        fout << Query(a,b) << "\n";
    }
    
    return 0;
}