#include <iostream>
#include <fstream>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <cctype>
#include <unordered_map>
#include <cmath>
#include <bitset>
#include <set>
#include <string>
#include <cstring>
#include <algorithm>
#include <deque>
#define INF 2140000000
#define MaxT 1000000
#define MaxN 16005
#define MaxM 100005
#define MAX 131072
#define MAXS 300005
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
int a[100005],b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,S,t,x,y,z,ok,nr,C,xc,yc,Min,w,poz,ans,cost,Max;
struct Tree{
   int sum,sum_dreapta,sum_stanga,sum_max;
};
Tree T[500005];
Tree UpdateNode(Tree left,Tree right){
      Tree NewT;
      NewT.sum=left.sum+right.sum;
      NewT.sum_dreapta=max(left.sum_dreapta,left.sum+right.sum_dreapta);
      NewT.sum_stanga=max(right.sum_stanga,right.sum+left.sum_stanga);
      NewT.sum_max=max(left.sum_stanga+right.sum_dreapta,max(left.sum_max,right.sum_max));
      return NewT;

}
void Build(int node,int left,int right){
     if(left==right){
        k++;
        T[node].sum=a[k];
        T[node].sum_dreapta=a[k];
        T[node].sum_stanga=a[k];
        T[node].sum_max=a[k];
     }
     else{
          int mid=(left+right)/2;
          Build(2*node,left,mid);
          Build(2*node+1,mid+1,right);
          T[node]=UpdateNode(T[2*node],T[2*node+1]);
     }
}
Tree Query(int node,int left,int right,int q_left,int q_right){
    if(q_left<=left && right<=q_right){
        return T[node];
    }
    else{
        int mid=(left+right)/2;
         if(q_right<=mid){
              return Query(2*node,left,mid,q_left,q_right);
         }
         if(q_left>=mid+1){
            return Query(2*node+1,mid+1,right,q_left,q_right);
         }
         Tree left_t=Query(2*node,left,mid,q_left,q_right);
         Tree right_t=Query(2*node+1,mid+1,right,q_left,q_right);
         return UpdateNode(left_t,right_t);
    }
}
int main()
{
  in>>n>>q;
  k=0;
  for(i=1;i<=n;i++){
    in>>a[i];
  }
  Build(1,1,n);
  for(i=1;i<=q;i++){
    in>>x>>y;
    out<<Query(1,1,n,x,y).sum_max<<'\n';
  }
  return 0;

}