#include <iostream>
#include <fstream>
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
const int MAX = 100000;
int v[MAX+1], s[MAX+1];
int main()
{
    int n,m;
    in>>n>>m;
    for(int i=0; i<n; ++i)
        in>>v[i];
    s[0]=v[0];
    for(int i=1; i<n; ++i)
        s[i]=s[i-1]+v[i];
    int x,y;
    for(int i=0; i<m; ++i)
    {
        in>>x>>y;
        if(x==y)
            out<<v[x-1]<<'\n';
        else
        {
            int mini=100000,maxi=0,poz=0, ok=0;
            for(int j=x-1; j<y; ++j)
            {
                if(s[j]>maxi)
                {
                    maxi=s[j];
                    poz=j;
                }
                if(s[j]<mini)
                    mini=s[j];
                if(s[j]<0)
                    ok=1;
            }
            if(ok==0)
                out<<maxi-mini<<'\n';
            else
            {
                int j=x-1;
                while(j<poz)
                {
                    if(s[j]<0)
                        maxi=maxi-s[j];
                    ++j;
                }
                out<<maxi<<'\n';
            }
        }
    }
    return 0;
}