#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MX = 400006;
const ll If = 1LL * MX * MX;

struct node
{
    ll best,mn,mx;
};

int n,m,x,y;
ll sol,min_val;
ll sum[MX];
node t[MX];

int Nextint()
{
    char S[100];
    int Num = 0,i = 0;
    bool Neg = 0;

    scanf("%s",S);

    if (S[0] == '-')
        Neg = 1,i++;

    for (;i < strlen(S);i++)
        Num = Num * 10 + (S[i] - '0');

    if (Neg)
        Num *= -1;

    return Num;
}

void build_tree(int idx,int left,int right)
{
    if (left == right)
    {
        t[idx].mx = sum[left];
        t[idx].mn = sum[left - 1];
        t[idx].best = sum[left] - sum[left - 1];
        return;
    }

    int middle = (left + right) / 2;

    build_tree(2 * idx,left,middle);
    build_tree(2 * idx + 1,middle + 1,right);

    t[idx].mx = max(t[2 * idx].mx,t[2 * idx + 1].mx);
    t[idx].mn = min(t[2 * idx].mn,t[2 * idx + 1].mn);
    t[idx].best = max(max(t[2 * idx].best,t[2 * idx + 1].best),t[2 * idx + 1].mx - t[2 * idx].mn);
}

void query(int idx,int left,int right)
{
    if (x <= left && right <= y)
    {
        sol = max(sol,t[idx].best);

        if (min_val < If)
           sol = max(sol,t[idx].mx - min_val);

        min_val = min(min_val,t[idx].mn);
        return;
    }

    int middle = (left + right) / 2;

    if (x <= middle)
       query(2 * idx,left,middle);

    if (middle < y)
       query(2 * idx + 1,middle + 1,right);
}

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

     n = Nextint();
     m = Nextint();

     for (int i = 1;i <= n;i++)
     {
         int x;

         x = Nextint();
         sum[i] = x + sum[i - 1];
     }

     build_tree(1,1,n);

     for (int i = 1;i <= m;i++)
     {
         sol = -If;
         min_val = If;

         x = Nextint();
         y = Nextint();
         query(1,1,n);

         printf("%lld\n",sol);
     }

  return 0;
}