#include <iostream>
#include <fstream>
#include <cmath>
#include <climits>
#include <stdio.h>
#define N_MAX 100004
#define N_SQ 320

using namespace std;

ifstream in ("sqeuencequery.in");
ofstream out ("sequencequery.out");

int n, m, sqn;
int arr[N_MAX], partialSum[N_MAX];

struct batogMinMax {
    int min, max, best;
}batog[N_SQ];

void buildSum (){
    partialSum[0] = arr[0];
    for (int i=1; i<n; ++i)
        partialSum[i] = partialSum[i-1] + arr[i];
}


int subsecvSumaMax (int left, int right){
    int sum = arr[left], maxSum = arr[left], start = 1;
    for (int i=left+1; i<=right; ++i){
        if (sum < 0){
            start = i;
            sum = 0;
        }
        sum += arr[i];
        if (sum > maxSum){
            maxSum = sum;
        }
    }
    return maxSum;
}

void buildBatog (){
    for (int i=0; i<n; i+=sqn){
        batog[i/sqn].best = subsecvSumaMax(i, i+sqn-1);
    }
    for (int i=0; i<n; ++i){
        batog[i/sqn].min = INT_MAX;
        batog[i/sqn].max = INT_MIN;
    }
    for (int i=0; i<n; ++i){
        batog[i/sqn].min = min(batog[i/sqn].min, partialSum[i]);
        batog[i/sqn].max = max(batog[i/sqn].max, partialSum[i]);
    }
}

int capeteInside (int left, int right){
    int minim = INT_MAX, maxim = INT_MIN;
    if (left % sqn == 0)
        minim = batog[left/sqn].min;
    else{
        for (int i=left; i/sqn == left/sqn; ++i)
            minim = min(minim, partialSum[i]);
    }

    if ((right+1) % sqn == 0)
        maxim = batog[right/sqn].max;
    else{
        for (int i=right; i/sqn == right/sqn; --i)
            maxim = max(maxim, partialSum[i]);
    }

    return maxim - minim;
}

int main (){
    FILE *in, *out;
    in = fopen ("sequencequery.in", "r");
    out = fopen ("sequencequery.out", "w");
    
    fscanf (in, "%d%d", &n, &m);
    sqn = sqrt(n);
    for (int i=0; i<n; ++i){ // ~!!!!! indici de la 0
        fscanf (in, "%d", &arr[i]);
    }

    buildSum();
    buildBatog();

    int x, y, rez, secondRez; // intervalul in care caut
    for (int i=1; i<=m; ++i){
        fscanf(in, "%d%d", &x, &y);
        if (x/sqn == y/sqn){
            rez = subsecvSumaMax(x-1, y-1);
        }
        else{
            rez = capeteInside(x-1, y-1);
           // secondRez = capeteNotInside(x-1, y-1);
           // rez = max(rez, secondRez);
        }
        fprintf (out, "%d \n", rez);
    }

    fclose (in);
    fclose (out);
    return 0;   
}

// int capeteNotInside (int left, int right){
//     int first, second, sum, maxSum, start;

//     first = left / sqn;
//     second = right / sqn;


//     for (int i=first; i<=second; ++i){
//         if (sum < 0){
//             start = i;
//             sum = 0;
//         }
//         sum += batog[i].best;
//         if (sum > maxSum){
//             maxSum = sum;
//         }
//     }

//     return maxSum;
// }