import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//import java.util.TreeMap;
class GSS1 {
static int segment_tree[];
static int array[];
// TODO Auto-generated method stub
int N
=Integer.
parseInt(br.
readLine().
trim()); array=new int[N];
for(int i=0;i<N;i++){
array
[i
]=Integer.
parseInt(st.
nextToken());}
segment_tree=new int[4*N];
build(1, 0, N-1);
//for(int i=0;i<2*N;i++)System.out.print(segment_tree[i]+" ");
//System.out.println();
int M
=Integer.
parseInt(br.
readLine().
trim()); StringBuilder sb=new StringBuilder();
for(int i=0;i<M;i++){
//TreeMap<Integer,Integer> tm=new TreeMap<Integer, Integer>();
int x
=Integer.
parseInt(st.
nextToken()); int y
=Integer.
parseInt(st.
nextToken()); int nas=query(1, 0, N-1, x-1, y-1);
sb.append(nas+"\n");
}
}
public static void build(int node,int a,int b){
if(a>b)return;//out of range
else if(a==b){
segment_tree[node]= array[a];
return;
}
build(node*2, a,(a+b)/2);
build(node*2+1, 1+(a+b)/2, b);
segment_tree
[node
]=Math.
max(segment_tree
[node
*2],
Math.
max(segment_tree
[node
*2+1],segment_tree
[node
*2]+segment_tree
[node
*2+1]));
}
public static int query(int node,int a,int b,int i,int j){
if(a>j || b<i || a>b)return -1000000000;
else if(a>=i && b<=j)return segment_tree[node];
int q1=query(node*2, a,(a+ b)/2, i, j);
int q2=query(node*2+1,1+(a+b)/2,b,i,j);
//System.out.println(q1+" "+q2+" "+Math.max(q1, Math.max(q2,q1+q2)));
return Math.
max(q1,
Math.
max(q2,q1
+q2
)); }
}
aW1wb3J0IGphdmEuaW8uQnVmZmVyZWRSZWFkZXI7CmltcG9ydCBqYXZhLmlvLklPRXhjZXB0aW9uOwppbXBvcnQgamF2YS5pby5JbnB1dFN0cmVhbVJlYWRlcjsKaW1wb3J0IGphdmEudXRpbC5TdHJpbmdUb2tlbml6ZXI7Ci8vaW1wb3J0IGphdmEudXRpbC5UcmVlTWFwOwoKCmNsYXNzIEdTUzEgewpzdGF0aWMgaW50IHNlZ21lbnRfdHJlZVtdOwpzdGF0aWMgaW50IGFycmF5W107CglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB0aHJvd3MgTnVtYmVyRm9ybWF0RXhjZXB0aW9uLCBJT0V4Y2VwdGlvbiB7CgkJLy8gVE9ETyBBdXRvLWdlbmVyYXRlZCBtZXRob2Qgc3R1YgpCdWZmZXJlZFJlYWRlciBicj1uZXcgQnVmZmVyZWRSZWFkZXIobmV3IElucHV0U3RyZWFtUmVhZGVyKFN5c3RlbS5pbikpOwppbnQgTj1JbnRlZ2VyLnBhcnNlSW50KGJyLnJlYWRMaW5lKCkudHJpbSgpKTsKIGFycmF5PW5ldyBpbnRbTl07ClN0cmluZ1Rva2VuaXplciBzdD1uZXcgU3RyaW5nVG9rZW5pemVyKGJyLnJlYWRMaW5lKCkudHJpbSgpKTsKZm9yKGludCBpPTA7aTxOO2krKyl7CglhcnJheVtpXT1JbnRlZ2VyLnBhcnNlSW50KHN0Lm5leHRUb2tlbigpKTsKfQpzZWdtZW50X3RyZWU9bmV3IGludFs0Kk5dOwpidWlsZCgxLCAwLCBOLTEpOwovL2ZvcihpbnQgaT0wO2k8MipOO2krKylTeXN0ZW0ub3V0LnByaW50KHNlZ21lbnRfdHJlZVtpXSsiICIpOwovL1N5c3RlbS5vdXQucHJpbnRsbigpOwppbnQgTT1JbnRlZ2VyLnBhcnNlSW50KGJyLnJlYWRMaW5lKCkudHJpbSgpKTsKU3RyaW5nQnVpbGRlciBzYj1uZXcgU3RyaW5nQnVpbGRlcigpOwpmb3IoaW50IGk9MDtpPE07aSsrKXsKCS8vVHJlZU1hcDxJbnRlZ2VyLEludGVnZXI+IHRtPW5ldyBUcmVlTWFwPEludGVnZXIsIEludGVnZXI+KCk7CglzdD1uZXcgU3RyaW5nVG9rZW5pemVyKGJyLnJlYWRMaW5lKCkudHJpbSgpKTsKCWludCB4PUludGVnZXIucGFyc2VJbnQoc3QubmV4dFRva2VuKCkpOwoJaW50IHk9SW50ZWdlci5wYXJzZUludChzdC5uZXh0VG9rZW4oKSk7CglpbnQgbmFzPXF1ZXJ5KDEsIDAsIE4tMSwgeC0xLCB5LTEpOwoJc2IuYXBwZW5kKG5hcysiXG4iKTsKfQoJU3lzdGVtLm91dC5wcmludGxuKHNiKTsKCX0KcHVibGljIHN0YXRpYyB2b2lkIGJ1aWxkKGludCBub2RlLGludCBhLGludCBiKXsKCWlmKGE+YilyZXR1cm47Ly9vdXQgb2YgcmFuZ2UKCWVsc2UgaWYoYT09Yil7CgkJc2VnbWVudF90cmVlW25vZGVdPSBhcnJheVthXTsKCQlyZXR1cm47Cgl9CglidWlsZChub2RlKjIsIGEsKGErYikvMik7CglidWlsZChub2RlKjIrMSwgMSsoYStiKS8yLCBiKTsKCXNlZ21lbnRfdHJlZVtub2RlXT1NYXRoLm1heChzZWdtZW50X3RyZWVbbm9kZSoyXSxNYXRoLm1heChzZWdtZW50X3RyZWVbbm9kZSoyKzFdLHNlZ21lbnRfdHJlZVtub2RlKjJdK3NlZ21lbnRfdHJlZVtub2RlKjIrMV0pKTsKCQp9CnB1YmxpYyBzdGF0aWMgaW50IHF1ZXJ5KGludCBub2RlLGludCBhLGludCBiLGludCBpLGludCBqKXsKCWlmKGE+aiB8fCBiPGkgfHwgYT5iKXJldHVybiAtMTAwMDAwMDAwMDsKCWVsc2UgaWYoYT49aSAmJiBiPD1qKXJldHVybiBzZWdtZW50X3RyZWVbbm9kZV07IAoJaW50IHExPXF1ZXJ5KG5vZGUqMiwgYSwoYSsgYikvMiwgaSwgaik7CglpbnQgcTI9cXVlcnkobm9kZSoyKzEsMSsoYStiKS8yLGIsaSxqKTsKCS8vU3lzdGVtLm91dC5wcmludGxuKHExKyIgIitxMisiICIrTWF0aC5tYXgocTEsIE1hdGgubWF4KHEyLHExK3EyKSkpOwoJcmV0dXJuIE1hdGgubWF4KHExLCBNYXRoLm1heChxMixxMStxMikpOwp9Cn0=