#include <bits/stdc++.h>
using namespace std;
int v[100005], i, j, n, m, sum, summax, x, y;
int main()
{
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");
    f >> n >> m;
    for(i = 1; i <= n; i ++)
        f >> v[i];
    for(i = 1; i <= m; i ++)
    {
         f >> x >> y;
         summax = INT_MIN;
         sum = 0;
         for(j = x; j <= y; j ++)
         {
             if(sum < 0) sum = v[j];
             else sum += v[j];
             if(sum > summax) summax = sum;
         }
         g << summax << "\n";
    }
    return 0;
}