//tonynater - SPOJ 2013

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

#define sz(x) ((int) x.size())

typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;

const double pi = 3.141592653589793;
const double tau = 6.283185307179586;
const double epsilon = 1e-6;

const int MAX_N = 50100;
const int MIN_VALUE = -(1<<30);

int N, M;

int A[MAX_N];

struct segment
{
    int tMax;
    int lMax;
    int rMax;
    int sum;
    
    segment()
    {
        tMax = lMax = rMax = sum = 0;
    }
    
    segment(int t, int l, int r, int s)
    {
        tMax = t;
        lMax = l;
        rMax = r;
        sum = s;
    }
};

segment tree[MAX_N*3];

segment merge(segment s1, segment s2) //s1 left of s2
{
    int tMax = max(s1.rMax+s2.lMax, max(s1.tMax, s2.tMax));
    int lMax = max(s1.sum + s2.lMax, s1.lMax);
    int rMax = max(s2.sum + s1.rMax, s2.rMax);
    int sum = s1.sum + s2.sum;
    
    return segment(tMax, lMax, rMax, sum);
}

void build(int n, int b, int e)
{
    if(b == e) tree[n] = segment(A[b], A[b], A[b], A[b]);
    else
    {
        build(2*n, b, (b+e)/2);
        build(2*n+1, (b+e)/2+1, e);
        
        tree[n] = merge(tree[2*n], tree[2*n+1]);
    }
}

segment query(int n, int b, int e, int x, int y)
{
    if(b > e || b > y || e < x) return segment(MIN_VALUE, MIN_VALUE, MIN_VALUE, MIN_VALUE);
    else if(x <= b && e <= y) return tree[n];
    else return merge(query(2*n, b, (b+e)/2, x, y), query(2*n+1, (b+e)/2+1, e, x, y));
}

int main (int argc, const char * argv[])
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
        cin >> A[i];
    
    build(1, 0, N-1);
    
    cin >> M;
    
    for(int i = 0; i < M; i++)
    {
        int x, y;
        cin >> x >> y;
        --x; --y;
        
        cout << query(1, 0, N-1, x, y).tMax << '\n';
    }
    
    return 0;
}