/* 
 * File:   sequencequery.cpp
 * Author: Mindyou
 *
 * Created on December 9, 2011, 5:16 PM
 */

#include <cstdio>

using namespace std;

const int NMAX = 1 << 17;
const long long INF = (long long) 100000 * 100000;

int N, M;
long long A[NMAX], Min[NMAX << 1], Max[NMAX << 1], MaxDif[NMAX << 1];

void build_tree(int l, int r, int nod)
{
    int k = (l + r) >> 1;
    if(l == r)
    {
        Min[nod] = Max[nod] = A[l];
        MaxDif[nod] = -INF;
        return;
    }
    
    build_tree(l, k, nod << 1);
    build_tree(k + 1, r, (nod << 1) | 1);
    
    Min[nod] = Min[nod << 1] < Min[(nod << 1) | 1] ? Min[nod << 1] : Min[(nod << 1) | 1];
    Max[nod] = Max[nod << 1] > Max[(nod << 1) | 1] ? Max[nod << 1] : Max[(nod << 1) | 1];
    
    MaxDif[nod] = MaxDif[nod << 1];
    if(MaxDif[(nod << 1) | 1] > MaxDif[nod])
        MaxDif[nod] = MaxDif[(nod << 1) | 1];
    if(Max[(nod << 1) | 1] - Min[(nod << 1)] > MaxDif[nod])
        MaxDif[nod] = Max[(nod << 1) | 1] - Min[(nod << 1)];
}

long long query_min(int l, int r, int x, int y, int nod)
{
    if(x > r || y < l)
        return INF;
    
    if(x <= l && y >= r)
        return Min[nod];
    
    int k = (l + r) >> 1;
    long long result = query_min(l, k, x, y, nod << 1);
    long long nresult = query_min(k + 1, r, x, y, (nod << 1) | 1);
    
    return result < nresult ? result : nresult;
}

long long query_max(int l, int r, int x, int y, int nod)
{
    if(x > r || y < l)
        return -INF;
    
    if(x <= l && y >= r)
        return Max[nod];
    
    int k = (l + r) >> 1;
    long long result = query_max(l, k, x, y, nod << 1);
    long long nresult = query_max(k + 1, r, x, y, (nod << 1) | 1);
    
    return result > nresult ? result : nresult;
}

long long query(int l, int r, int x, int y, int nod)
{   
    if(x > r || y < l)
        return -INF;
    
    if(x <= l && r <= y)
        return MaxDif[nod];
    
    int k = (l + r) >> 1; 
    long long result, nvalue;
    long long leftmin, rightmax;
    
    result = query(l, k, x, y, nod << 1);
    nvalue = query(k + 1, r, x, y, (nod << 1) | 1);
    
    leftmin = query_min(l, k, x, y, nod << 1);
    rightmax = query_max(k + 1, r, x, y, (nod << 1) | 1);
    
    result = result < (rightmax - leftmin) ? rightmax - leftmin : result;
    
    return result < nvalue ? nvalue : result;
}
/*
 * 
 */
int main(int argc, char** argv) {

    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    
    scanf("%d %d ", &N, &M);
    
    A[0] = 0;
    for(int i = 0; i < N; i++)
    {
        int a;
        
        scanf("%d ", &a);
        A[i + 1] = A[i] + a;
    }
    
    build_tree(0, N, 1);
    
    for(; M--; )
    {
        int a, b;
        
        scanf("%d %d ", &a, &b);
        printf("%lld\n", query(0, N, a - 1, b, 1));
    }
    return 0;
}