#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define dl double long
using namespace std;
const int N = 5e5 + 7;
const int M = 20 + 7;
const ll mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,q;
int a[N];
int ans[N];
int t[4 * N];
int lz[4 * N];
int tt[4 * N];
vector < pair < int , int > > v[N];
void mx( int &x , int y )
{
x = max( x , y );
}
void push( int x )
{
mx( t[x + x] , t[x] );
mx( t[x + x + 1] , t[x] );
mx( tt[x + x] , t[x + x] + lz[x + x] );
mx( tt[x + x + 1] , t[x + x + 1] + lz[x + x + 1] );
mx( tt[x] , tt[x + x] );
mx( tt[x] , tt[x + x + 1] );
}
void build( int x , int l , int r )
{
if( l == r ){
lz[x] = a[l];
return;
}
int m = (l + r) / 2;
build( x + x , l , m );
build( x + x + 1 , m + 1 , r );
mx( lz[x] , lz[x + x] );
mx( lz[x] , lz[x + x + 1] );
}
void upd( int x , int l , int r, int tl , int tr , int val )
{
if( tl > tr )return;
if( l == tl && r == tr ){
mx( t[x] , val );
mx( tt[x] , t[x] + lz[x] );
return;
}
push(x);
int m = (l + r) / 2;
upd( x + x , l , m , tl , min( tr , m ) , val );
upd( x + x + 1 , m + 1 , r , max( tl , m + 1 ) , tr , val );
mx( tt[x] , tt[x + x] );
mx( tt[x] , tt[x + x + 1] );
}
int get( int x , int l , int r , int tl , int tr )
{
if( tl > tr )return 0;
if( l == tl && r == tr ){
return tt[x];
}
int m = (l + r) / 2;
push(x);
return max( get( x + x , l , m , tl , min( tr , m ) ) ,
get( x + x + 1 , m + 1 , r , max( tl , m + 1 ) , tr ) );
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen( "input.txt" , "r" , stdin );
//freopen( "output.txt" , "w" , stdout );
cin >> n;
for( int i = 1; i <= n; i++ ){
cin >> a[i];
}
stack < int > st;
vector < pair < int , int > > pr;
for( int i = 1; i < n; i++ ){
while( !st.empty() && a[st.top()] <= a[i] ){
pr.push_back({ st.top() , i });
st.pop();
}
if( !st.empty() )pr.push_back({ st.top() , i });
st.push(i);
}
build( 1 , 1 , n );
sort( pr.rbegin() , pr.rend() );
cin >> q;
for( int i = 1; i <= q; i++ ){
int l,r;
cin >> l >> r;
v[l].push_back({r , i});
}
for( int i = n , j = 0; i >= 1; i-- ){
while( j < (int)pr.size() && pr[j].fi >= i ){
upd( 1 , 1 , n , pr[j].se + (pr[j].se - pr[j].fi) , n , a[pr[j].fi] + a[pr[j].se] );
j += 1;
}
for( auto x : v[i] ){
ans[x.se] = get( 1 , 1 , n , i , x.fi );
}
}
for( int i = 1; i <= q; i++ ){
cout << ans[i] << "\n";
}
}
