#include <cstdio>
        #include <cstring>
        using namespace std;
        int a[100001], sum[100001], best[100001];
        int main()
        {
            int n, m, x, y, i, l, p=1, r=1, Min, Max;
            freopen("sequencequery.in","r",stdin);
            freopen("sequencequery.out","w",stdout);
            scanf("%d%d",&n,&m);
            for (i=1; i<=n; i++) scanf("%d",&a[i]);
            for (i=1; i<=n; i++) sum[i]=sum[i-1]+a[i];
            for (l=1; l<=m; l++)
            {
                scanf("%d%d",&x,&y); Min=0; Max=-2000000000;
                memset(best,0,sizeof(best)); memset(sum,0,sizeof(sum));
                for (i=x; i<=y; i++) sum[i]=sum[i-1]+a[i];
                for (i=x; i<=y; i++)
                {
                    best[i]=sum[i]-Min;
                    if (sum[i]<Min) {Min=sum[i]; p=i+1;}
                    if (best[i]>Max)
                    {
                        Max=best[i]; r=i;
                        if (p>i) p--;
                    }
                }
                printf("%d\n",Max);
            }
            fclose(stdin);
            fclose(stdout);
            return 0;
        }