#include <cstdio>
#include <algorithm>
using namespace std;
#define lf (2*n)
#define rt (2*n+1)
#define MAX 200002
#define MAY 1<<19
#define INF 0xfffffff

int n,m,x,y,aib[MAX], p[MAY], u[MAY], s[MAY], d[MAY], rs ,last;

void update(int idx,int val){
    while( idx <= n )
    {
        aib[idx] += val;
        idx += idx&-idx;
    }
}

int read(int idx){
    int sum = 0;
    while( idx > 0 )
    {
        sum += aib[idx];
        idx -= idx&-idx;
    }
    return sum;
}

void build(int n,int l,int r){
    if(l == r)
    {
        p[n] = u[n] = s[n] = d[n] = r;
        return ;
    }
        int m = (l+r)/2;
        build(lf,l,m);
        build(rt,m+1,r);
        if(read(r)-read(d[lf]-1) > read(r) - read(d[rt]-1))d[n] = d[lf]; else d[n] = d[rt];
        if(read(s[rt])-read(l-1) > read(s[lf])-read(l-1))s[n] = s[rt]; else s[n] = s[lf];
        int s1 = read(u[lf])-read(p[lf]-1), s2 = read(u[rt])-read(p[rt]-1);
        if(s1 > s2) { p[n] = p[lf]; u[n] = u[lf]; } else { p[n] = p[rt]; u[n] = u[rt]; s1 = s2; }
        s2 = read(s[rt])-read(d[lf]-1);
        if(s2 > s1) { p[n] = d[lf]; u[n] = s[rt]; }
}

void query(int n,int l,int r){
    if(x<=l && r<=y)
    {
        rs = max(rs, read(u[n])-read(p[n]-1));
        rs = max(rs, read(s[n])-read(last-1));
        if(read(r)-read(last-1)<read(r)-read(d[n]-1))last = d[n];
        return;
    }
        int m = (l+r)/2;
        if(x <= m)query(lf,l,m);
        if(y > m) query(rt,m+1,r);
}

int main(){
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            update(i,x);
        }
    build(1,1,n);

    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        last = x; rs = -INF;
        query(1,1,n);
        printf("%d\n",rs);
    }
       /* scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
          //  scanf("%d %d",&x,&y);
          //  printf("%d\n",read(y)-read(x-1));
        } */
    return 0;
}