#include <fstream>
#include <vector>
#include <limits>
using namespace std;

ifstream is("sequencequery.in");
ofstream os("sequencequery.out");

struct Arb{
    long long left, right, sum, answ;
};

vector<Arb> A;
int n, st, dr, m;
int val, pos;
long long fAnsw, asum;

void Update(int l, int r, int node);
void Query(int l, int r, int node);
void Read();

int main()
{
    Read();
    Update(1, n, 1);
    for ( int i = 1; i <= m; ++i )
    {
        is >> st >> dr;
        fAnsw = -(1LL << 60);
        asum = 0;
        Query(1, n, 1);
        os << fAnsw << '\n';

    }
    is.close();
    os.close();
    return 0;
}

void Update(int l, int r, int node)
{
    if ( l == r )
    {
        A[node].left = A[node].right = A[node].sum = A[node].answ = val;
        return;
    }
    int mid = (l + r) / 2;
    if ( pos <= mid )
        Update(l, mid, 2 * node);
    else
        Update(mid + 1, r, 2 * node + 1);

    A[node].left = max(A[2 * node].left, A[2 * node + 1].left + A[2 * node].sum);
    A[node].right = max(A[2 * node + 1].right, A[2 * node].right + A[2 * node + 1].sum);
    A[node].answ = max(A[2 * node].right + A[2 * node + 1].left, max(A[2 * node].answ, A[2 * node + 1].answ));
    A[node].sum = A[2 * node].sum + A[2 * node + 1].sum;
}

void Query(int l, int r, int node)
{
    if ( st <= l && r <= dr )
    {
        fAnsw = max(fAnsw, max(asum + A[node].left, A[node].answ));
        asum = max(asum + A[node].sum, A[node].right);
        return;
    }

    int mid = (l + r) / 2;
    if ( st <= mid )
        Query(l, mid, 2 * node);
    if ( dr > mid )
        Query(mid + 1, r, 2 * node + 1);
}

void Read()
{
    is >> n;
    A = vector<Arb>(4 * n + 5);
    for ( int i = 1; i <= n; ++i )
    {
        is >> val;
        pos = i;
        Update(1, n, 1);
    }
}