#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
const int N = 1e5+5;
ll n, m, cm[N], x;
pair<ll, pair<ll, ll>> seg[4*N];
void build(int l=0, int r=N, int idx=1)
{
    if(l == r)
    {
        seg[idx].f = -1e11;
        seg[idx].s.f = seg[idx].s.s = cm[l];
        return;
    }
    int mid = (l+r)>>1;
    build(l, mid, idx*2);
    build(mid+1, r, idx*2+1);
    seg[idx].f = max(seg[idx*2].f, seg[idx*2+1].f);
    seg[idx].f = max(seg[idx].f, seg[idx*2+1].s.s - seg[idx*2].s.f);
    seg[idx].s.f = min(seg[idx*2].s.f, seg[idx*2+1].s.f);
    seg[idx].s.s = max(seg[idx*2].s.s, seg[idx*2+1].s.s);
}
pair<ll, pair<ll, ll>> query(int x, int y, int l=0, int r=N, int idx=1)
{
    if(l > y || r < x) return {-1e11, {1e11, -1e11}};
    if(l >= x && r <= y) return seg[idx];
    int mid = (l+r)>>1;
    auto L = query(x, y, l, mid, idx*2);
    auto R = query(x, y, mid+1, r, idx*2+1);
    pair<ll, pair<ll, ll>> A = {max(L.f, max(R.f, R.s.s - L.s.f)), {min(R.s.f, L.s.f), max(R.s.s, L.s.s)}};
    return A;
}
int main()
{
    freopen("sequencequery.in", "rt", stdin);
    freopen("sequencequery.out", "wt", stdout);
    cin >> n >> m;
    for(int i=0; i<n; i++) scanf("%lld", &x), cm[i+1] = cm[i]+x;
    build();
    while(m--)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        auto q = query(l-1, r);
        printf("%lld\n", q.f);
    }
}