#include <fstream>
#include <climits>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int sir[100000];
int n, m;

//folosim algoritum lui Kadane
int sumSubsir(int x, int y){//O(n)
    int sum = 0, sumMax = INT_MIN;
    for(int k = x - 1; k < y; ++k){
        sum = max(sir[k], sum + sir[k]);
        sumMax = max(sumMax, sum);
    }
    return sumMax;
}

int main(){
    fin >> n >> m;
    for(int i = 0; i < n; ++i){//O(n)
        fin >> sir[i];
    }
    for(int i = 0; i < m; ++i){//O(n)
        int x, y;
        fin >> x >> y;
        fout << sumSubsir(x, y) << '\n';//O(n)
    }
    return 0;
}