#include <stdio.h>
#define LIM 131072
#include <ctype.h>
//solutia cu parsare
using namespace std;
FILE *fi, *fo;
struct padure{
  long long pref, suf, sum, ssm;
  inline void reset(long long val){
    pref=sum=ssm=suf=val;
  }
} copac[400000];

int a, b, poz=LIM, poz2=0;
char BUF[LIM], BUF2[LIM];

inline char getChar(){
  poz++;
  if(poz>=LIM){
    fread(BUF,LIM,1,fi);
    poz=0;
  }
  return BUF[poz];
}

inline int getNr(){
  int r=0, semn=1;
  char ch=getChar();
  while(isdigit(ch)==0 && ch!='-') ch=getChar();
  if(ch=='-'){
    semn=-1;
    ch=getChar();
  }
  while(isdigit(ch)!=0){
    r=r*10+semn*(ch-'0');
    ch=getChar();
  }
  return r;
}

inline void putch(char ch){
  BUF2[poz2++]=ch;
  if(poz2==LIM){
    fwrite(BUF2,LIM,1,fo);
    poz2=0;
  }
}

inline void baga(long long x){
  char s[15];
  int k=0;
  if(x<0){
    putch('-');
    x=-x;
  }
  do{
    s[k++]=x%10+'0';
    x/=10;
  }while(x);
  while(k>0){
    k--;
    putch(s[k]);
  }
}

inline long long maxim(long long a, long long b){
  if(a<b)
    return b;
  return a;
}

inline struct padure calcul(struct padure a, struct padure b){
  struct padure rez;
  rez.pref = maxim ( a.pref, a.sum+b.pref );
  rez.suf = maxim ( b.suf, a.suf+b.sum );
  rez.sum = a.sum + b.sum;
  rez.ssm = maxim( maxim( a.ssm, b.ssm ), a.suf+b.pref );
  return rez;
}

void add(int nod, int st, int dr){
  if(st==dr && st==a){
    copac[nod].reset(b);
    return;
  }
  int div=(dr+st)/2;
  if(a<=div)
    add(2*nod,st,div);
  else
    add(2*nod+1,div+1,dr);
  copac[nod]=calcul(copac[2*nod],copac[2*nod+1]);
}

struct padure query(int nod, int st, int dr){
  if(a<=st && dr<=b){
    return copac[nod];
  }
  int div=dr+st;
  struct padure rez;
  div/=2;
  rez.reset(-1000000000000);
  if(a<=div)
    rez=query(2*nod,st,div);
  if(b>div)
    rez=calcul(rez,query(2*nod+1,div+1,dr));
  return rez;
}


int main()
{
  int n, m, i;
  fi=fopen("sequencequery.in", "r");
  fo=fopen("sequencequery.out", "w");
  n=getNr(); m=getNr();
  for(i=1;i<=n;i++){
    a=i;
    b=getNr();
    add(1,1,n);
  }
  for(i=1;i<=m;i++){
    a=getNr(); b=getNr();
    baga( query(1,1,n).ssm );
    putch('\n');
  }
  if(poz2>0)
    fwrite(BUF2,poz2,1,fo);
  fclose(fi);
  fclose(fo);
  return 0;
}