/* 
 * 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)];
}

void query(int l, int r, int x, int y, int nod, long long* maxdif, long long* min, long long * max)
{   
    if(x > r || y < l)
    {
        *maxdif = -INF;
        *min = INF;
        *max = -INF;
        return;
    }
    
    if(x <= l && r <= y)
    {
        *maxdif = MaxDif[nod];
        *min = Min[nod];
        *max = Max[nod];
        return;
    }
    
    int k = (l + r) >> 1; 
    long long result, min_res_left, max_res_left, min_res_right, max_res_right;
    long long nvalue;
    
    query(l, k, x, y, nod << 1, &result, &min_res_left, &max_res_left);
    query(k + 1, r, x, y, (nod << 1) | 1, &nvalue, &min_res_right, &max_res_right);
    
    result = result < (max_res_right - min_res_left) ? max_res_right - min_res_left : result;
    result = result < nvalue ? nvalue : result;
    
    *maxdif = result;
    *min = min_res_left < min_res_right ? min_res_left : min_res_right;
    *max = max_res_left > max_res_right ? max_res_left : max_res_right;
}
/*
 * 
 */
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);
        long long x, y, z;
        
        query(0, N, a - 1, b, 1, &x, &y, &z);
        printf("%lld\n", x);
    }
    return 0;
}