#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f
#define ll long long
struct Node {
ll int maxPrefixSum;
ll int maxSuffixSum;
ll int totalSum;
ll int maxSubarraySum;
Node()
{
maxPrefixSum = maxSuffixSum = maxSubarraySum = -inf;
totalSum = -inf;
}
};
Node merge(Node leftChild, Node rightChild)
{
Node parentNode;
parentNode.maxPrefixSum = max(leftChild.maxPrefixSum,
leftChild.totalSum +
rightChild.maxPrefixSum);
parentNode.maxSuffixSum = max(rightChild.maxSuffixSum,
rightChild.totalSum +
leftChild.maxSuffixSum);
parentNode.totalSum = leftChild.totalSum +
rightChild.totalSum;
parentNode.maxSubarraySum = max({leftChild.maxSubarraySum,
rightChild.maxSubarraySum,
leftChild.maxSuffixSum +
rightChild.maxPrefixSum});
return parentNode;
}
void constructTreeUtil(Node* tree,ll int arr[],ll int start,
ll int end,ll int index)
{
if (start == end) {
tree[index].totalSum = arr[start];
tree[index].maxSuffixSum = arr[start];
tree[index].maxPrefixSum = arr[start];
tree[index].maxSubarraySum = arr[start];
return;
}
ll int mid = (start + end) / 2;
constructTreeUtil(tree, arr, start, mid, 2 * index);
constructTreeUtil(tree, arr, mid + 1, end, 2 * index + 1);
tree[index] = merge(tree[2 * index], tree[2 * index + 1]);
}
Node* constructTree(ll int arr[],ll int n)
{
Node* tree = new Node[4*n+1];
constructTreeUtil(tree, arr, 0, n - 1, 1);
return tree;
}
Node queryUtil(Node* tree,ll int ss,ll int se, ll int qs,
ll int qe,ll int index)
{
// No overlap
if (ss > qe || se < qs) {
// returns a Node for out of bounds condition
Node nullNode;
return nullNode;
}
// Complete overlap
if (ss >= qs && se <= qe) {
return tree[index];
}
ll int mid = (ss + se) / 2;
Node left = queryUtil(tree, ss, mid, qs, qe,
2 * index);
Node right = queryUtil(tree, mid + 1, se, qs,
qe, 2 * index + 1);
Node res = merge(left, right);
return res;
}
ll int query(Node* tree,ll int start,ll int end,ll int n)
{
Node res = queryUtil(tree, 0, n - 1, start, end, 1);
return res.maxSubarraySum;
}
int main()
{
ll int n ;
cin>>n;
ll int arr[n];
ll int i;
for(i=0;i<n;i++){
cin>>arr[i];
}
Node* Tree = constructTree(arr, n);
ll int start, end, maxSubarraySum;
ll int q;
cin>>q;
while(q--){
ll int start,end;
cin>>start>>end;
cout<<query(Tree, start-1, end-1, n)<<"\n";
}
return 0;
}