#include<stdio.h>
#include<algorithm>
#define maxn 100005
#define maxait 1<<20
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;

struct seg_tree{ll sl,sr,sum,smax;} ait[maxait],sol;
int n,m;
ll a[maxn];

void build(int k,int left,int right)
{
    if(left==right)
    {ait[k].sl=ait[k].sr=ait[k].sum=ait[k].smax=a[left]; return;}

    int mid=(left+right)>>1;
    build(2*k,left,mid);
    build(2*k+1,mid+1,right);

    ait[k].sl=max(ait[2*k].sl,ait[2*k].sum+ait[2*k+1].sl);
    ait[k].sr=max(ait[2*k+1].sr,ait[2*k+1].sum+ait[2*k].sr);
    ait[k].sum=ait[2*k].sum+ait[2*k+1].sum;
    ait[k].smax=max(max(ait[2*k].smax,ait[2*k+1].smax),ait[2*k].sr+ait[2*k+1].sl);
}

void update_sol(int k,int left,int right)
{
    if(sol.smax==-inf) {sol=ait[k]; return;}
    seg_tree aux;
    aux.sl=max(sol.sl,sol.sum+ait[k].sl);
    aux.sr=max(ait[k].sr,ait[k].sum+sol.sr);
    aux.sum=sol.sum+ait[k].sum;
    aux.smax=max(max(sol.smax,ait[k].smax),sol.sr+ait[k].sl);
    sol=aux;
}

void query(int k,int left,int right,int x,int y)
{
    if( x<=left && right<=y ) {update_sol(k,left,right); return;}
    int mid=(left+right)>>1;
    if(x<=mid) query(2*k,left,mid,x,y);
    if(y>mid) query(2*k+1,mid+1,right,x,y);
}

void read()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
}

void solve()
{
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        if(x>y) swap(x,y);
        sol.smax=-inf;
        query(1,1,n,x,y);
        printf("%lld\n",sol.smax);
    }
}

int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);

    read();
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}