#include <bits/stdc++.h>
using namespace std ;
const int MAX = 5e5 + 10 ;
int arr[MAX] ;
int n ;
vector< pair<int , int> >queries[MAX] ;
vector<int>v[MAX] ;
int ans[MAX] ;
struct Node
{
int x = 0 , y = 0 , val = 0 ;
};
Node tree[4 * MAX] ;
Node Merge(Node &a , Node &b)
{
Node c ;
c.x = max(a.x , b.x) ;
c.y = max(a.y , b.y) ;
c.val = max({a.val , b.val , a.y + b.x}) ;
return c ;
}
void build(int node , int l , int r)
{
if(l == r)
{
tree[node].x = arr[l] ;
tree[node].val = tree[node].x + tree[node].y ;
return ;
}
int mid = (l + r) >> 1 ;
build(node << 1 , l , mid) ;
build(node << 1 | 1 , mid+1 , r) ;
tree[node] = Merge(tree[node << 1] , tree[node << 1 | 1]) ;
}
void update(int node , int l , int r , int idx , int val)
{
if(idx > r || idx < l)
return ;
if(l == r)
{
tree[node].y = max(tree[node].y , val) ;
tree[node].val = tree[node].x + tree[node].y ;
return ;
}
int mid = (l + r) >> 1 ;
update(node << 1 , l , mid , idx , val) ;
update(node << 1 | 1 , mid+1 , r , idx , val) ;
tree[node] = Merge(tree[node << 1] , tree[node << 1 | 1]) ;
}
Node tmp ;
Node query(int node , int l , int r , int from , int to)
{
if(from > r || to < l)
return tmp ;
if(l >= from && r <= to)
return tree[node] ;
int mid = (l + r) >> 1 ;
Node x = query(node << 1 , l , mid , from , to) ;
Node y = query(node << 1 | 1 , mid+1 , r , from , to) ;
return Merge(x , y) ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 1 ; i <= n ; ++i)
cin>>arr[i] ;
int q ;
cin>>q ;
for(int i = 1 ; i <= q ; ++i)
{
int l , r ;
cin>>l>>r ;
queries[l].emplace_back(r , i) ;
}
stack<int>s ;
for(int i = 1 ; i <= n ; ++i)
{
while(s.size() && arr[i] >= arr[s.top()])
v[s.top()].push_back(i) , s.pop() ;
if(s.size())
v[s.top()].push_back(i) ;
s.push(i) ;
}
build(1 , 1 , n) ;
for(int i = n ; i >= 1 ; --i)
{
for(auto &j : v[i])
{
if(2*j - i <= n)
update(1 , 1 , n , 2*j - i , arr[i] + arr[j]) ;
}
for(auto &p : queries[i])
ans[p.second] = query(1 , 1 , n , i+2 , p.first).val ;
}
for(int i = 1 ; i <= q ; ++i)
cout<<ans[i]<<"\n" ;
return 0 ;
}
