#include <bits/stdc++.h>

using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

int n, m;
long long a[100001], sp[100003];

int main()
{
    f >> n >> m;
    for(int i = 1 ; i <= n; ++i) {
        f >> a[i];
        sp[i] = a[i] + sp[i - 1];
    }
    for(int i = 1; i <= m; ++i) {
        long long s = 0, smax = -100000000000000002;
        int x, y;
        f >> x >> y;
        for(int j = x; j <= y; ++j) {
            if(a[j] + s < a[j]) {
                s = a[j];
            }

        else {
            s += a[j];
        }
        if(s > smax) {
            smax = s;
        }
        }
        g << smax << '\n';
    }
}