#include <bits/stdc++.h>
using namespace std;
struct ab {
int a, b;
};
const int inf = 4e8;
struct info {
int maxAB, maxC, maxABC;
info operator + ( const info &x ) const {
info ans;
ans.maxAB = max( maxAB, x.maxAB );
ans.maxC = max( maxC, x.maxC );
ans.maxABC = max( max( maxABC, x.maxABC ), maxAB + x.maxC );
return ans;
}
};
struct update {
int pos, val;
};
struct query {
int l, r, p;
};
const int MAX_N = 5e5;
const int MAX_Q = 5e5;
int val[MAX_N + 1], ans[MAX_Q];
vector<ab> pairs;
vector<update> updates[MAX_N + 1];
vector<query> queries[MAX_N + 1];
struct SegTree {
info segTree[4 * MAX_N];
void init( int v, int l, int r ) {
if ( l == r ) {
segTree[v] = { -inf, val[l], -inf };
return;
}
int mid = (l + r) / 2;
init( v * 2 + 1, l, mid );
init( v * 2 + 2, mid + 1, r );
segTree[v].maxC = max( segTree[v * 2 + 1].maxC, segTree[v * 2 + 2].maxC );
}
void update( int v, int l, int r, int pos, int val ) {
if ( l > pos || r < pos )
return;
if ( l == r ) {
segTree[v].maxAB = max( segTree[v].maxAB, val );
segTree[v].maxABC = segTree[v].maxAB + segTree[v].maxC;
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, pos, val );
update( v * 2 + 2, mid + 1, r, pos, val );
segTree[v] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
//printf( "udpate %d %d %d %d %d\n", l, r, segTree[v].maxAB, segTree[v].maxC, segTree[v].maxABC );
}
info query( int v, int l, int r, int lq, int rq ) {
if ( l > rq || r < lq )
return { -inf, -inf, -inf };
if ( lq <= l && r <= rq ) {
//printf( "query %d %d %d %d %d\n", l, r, segTree[v].maxAB, segTree[v].maxC, segTree[v].maxABC );
return segTree[v];
}
int mid = (l + r) / 2;
return query( v * 2 + 1, l, mid, lq, rq ) + query( v * 2 + 2, mid + 1, r, lq, rq );
}
};
SegTree maxJump;
int main() {
int n;
cin >> n;
for ( int i = 1; i <= n; i++ )
cin >> val[i];
stack <int> s;
for ( int i = 1; i <= n; i++ ) {
while ( !s.empty() && val[i] >= val[s.top()] ) {
pairs.push_back( { s.top(), i } );
s.pop();
}
if ( !s.empty() )
pairs.push_back( { s.top(), i } );
s.push( i );
}
for ( ab x: pairs )
updates[x.a].push_back( { 2 * x.b - x.a, val[x.a] + val[x.b] } );//, printf( "%d %d\n", x.a, x.b );
int q;
cin >> q;
for ( int i = 0; i < q; i++ ) {
int l, r;
cin >> l >> r;
queries[l].push_back( { l, r, i } );
}
maxJump.init( 0, 1, n );
for ( int i = n; i >= 1; i-- ) {
for ( update u: updates[i] )
maxJump.update( 0, 1, n, u.pos, u.val );//, printf( "u %d %d %d\n", i, u.pos, u.val );
for ( query q: queries[i] )
ans[q.p] = maxJump.query( 0, 1, n, q.l, q.r ).maxABC;//, printf( "q %d %d %d %d\n", i, q.l, q.r, q.p );
}
for ( int i = 0; i < q; i++ )
cout << ans[i] << "\n";
return 0;
}
