import java.io.DataInputStream ;
import java.io.IOException ;
class GSS1NODE {
final int N = s.nextInt ( ) ;
int input[ ] = new int [ N] ;
for ( int i = 0 ; i < N; i++ ) {
input[ i] = s.nextInt ( ) ;
}
GSS1NODE obj= new GSS1NODE( ) ;
obj.buildUtility ( input) ;
}
GSS1NODE obj= new GSS1NODE( ) ;
int len= input.length ;
Node segTree[ ] = new Node[ maxSize] ;
for ( int i = 0 ; i < maxSize ; i++ ) {
segTree[ i] = new Node( ) ;
}
obj.buildTree ( input,0 ,len- 1 ,0 ,segTree) ;
/*System.out.println();
for (int i = 0; i <maxSize ; i++) {
System.out.print(segTree[i].B+" ");
}*/
int M = s.nextInt ( ) ;
while ( M-- > 0 ) {
Node temp= obj.query ( s.nextInt ( ) - 1 , s.nextInt ( ) - 1 , 0 , len- 1 , 0 ,segTree) ;
}
}
void buildTree( int input[ ] ,int low,int high,int pos,Node segTree[ ] ) {
if ( low> high)
return ;
if ( low== high) {
Node newNode= new Node( ) ;
newNode.B = input[ low] ;
newNode.L = input[ low] ;
newNode.R = input[ low] ;
newNode.T = input[ low] ;
segTree[ pos] = newNode;
return ;
}
GSS1NODE obj= new GSS1NODE( ) ;
int mid= ( low+ high) / 2 ;
int left= pos* 2 + 1 ,right= pos* 2 + 2 ;
buildTree( input,low,mid,left,segTree) ;
buildTree( input,mid+ 1 ,high,right,segTree) ;
segTree[ pos] = obj.join ( segTree[ left] ,segTree[ right] ) ;
}
Node join( Node left,Node right) {
GSS1NODE obj= new GSS1NODE( ) ;
Node newNode= new Node( ) ;
newNode.
L = Math .
max ( left.
L ,left.
T + right.
L ) ; newNode.
R = Math .
max ( left.
R + right.
T ,right.
R ) ; newNode.T = left.T + right.T ;
newNode.B = obj.max3 ( left.B ,right.B ,left.R + right.L ) ;
return newNode;
}
Node query( int qlow,int qhigh,int low,int high,int pos,Node segTree[ ] ) {
//no overlap
if ( qlow> high || low> qhigh) {
return new Node( ) ;
}
//total overlap
if ( low>= qlow && high<= qhigh)
return segTree[ pos] ;
//partial overlap
GSS1NODE obj= new GSS1NODE( ) ;
int mid= ( low+ high) / 2 ;
int left= pos* 2 + 1 ,right= pos* 2 + 2 ;
return obj.join ( query( qlow,qhigh,low,mid,left,segTree) ,query( qlow,qhigh,mid+ 1 ,high,right,segTree) ) ;
}
int max3( int a,int b,int c) {
}
class Node{
int L,R,T,B;
Node( ) {
L=- 15008 ;
R=- 15008 ;
T=- 15008 ;
B=- 15008 ;
}
}
{
final private int BUFFER_SIZE = 1 << 16 ;
private byte [ ] buffer;
private int bufferPointer, bytesRead;
{
buffer = new byte [ BUFFER_SIZE] ;
bufferPointer = bytesRead = 0 ;
}
{
byte [ ] buf = new byte [ 64 ] ; // line length
int cnt = 0 , c;
while ( ( c = read( ) ) != - 1 )
{
if ( c == '\n ' )
break ;
buf[ cnt++ ] = ( byte ) c;
}
return new String ( buf,
0 , cnt
) ; }
{
int ret = 0 ;
byte c = read( ) ;
while ( c <= ' ' )
c = read( ) ;
boolean neg = ( c == '-' ) ;
if ( neg)
c = read( ) ;
do
{
ret = ret * 10 + c - '0' ;
} while ( ( c = read( ) ) >= '0' && c <= '9' ) ;
if ( neg)
return - ret;
return ret;
}
{
bytesRead = din.read ( buffer, bufferPointer = 0 , BUFFER_SIZE) ;
if ( bytesRead == - 1 )
buffer[ 0 ] = - 1 ;
}
{
if ( bufferPointer == bytesRead)
fillBuffer( ) ;
return buffer[ bufferPointer++ ] ;
}
}
}
aW1wb3J0IGphdmEuaW8uRGF0YUlucHV0U3RyZWFtOwppbXBvcnQgamF2YS5pby5JT0V4Y2VwdGlvbjsKCmNsYXNzIEdTUzFOT0RFIHsKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZyBhcmdzW10pdGhyb3dzIElPRXhjZXB0aW9uIHsKICAgICAgICBSZWFkZXIgcyA9IG5ldyBSZWFkZXIoKTsKICAgICAgICBmaW5hbCBpbnQgTiA9IHMubmV4dEludCgpOwogICAgICAgIGludCBpbnB1dFtdID0gbmV3IGludFtOXTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykgewogICAgICAgICAgICBpbnB1dFtpXSA9IHMubmV4dEludCgpOwogICAgICAgIH0KICAgICAgICBHU1MxTk9ERSBvYmo9bmV3IEdTUzFOT0RFKCk7CiAgICAgICAgb2JqLmJ1aWxkVXRpbGl0eShpbnB1dCk7CiAgICB9CiAgICB2b2lkIGJ1aWxkVXRpbGl0eShpbnQgaW5wdXRbXSl0aHJvd3MgSU9FeGNlcHRpb257CiAgICAgICAgR1NTMU5PREUgb2JqPW5ldyBHU1MxTk9ERSgpOwogICAgICAgIGludCBsZW49aW5wdXQubGVuZ3RoOwogICAgICAgIGludCBtYXhTaXplPTIqKGludClNYXRoLnBvdygyLChpbnQpTWF0aC5jZWlsKE1hdGgubG9nKGxlbikvTWF0aC5sb2coMikpKS0xOwogICAgICAgIE5vZGUgc2VnVHJlZVtdPW5ldyBOb2RlW21heFNpemVdOwoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8bWF4U2l6ZSA7IGkrKykgewogICAgICAgICAgICBzZWdUcmVlW2ldPW5ldyBOb2RlKCk7CiAgICAgICAgfQoKICAgICAgICBvYmouYnVpbGRUcmVlKGlucHV0LDAsbGVuLTEsMCxzZWdUcmVlKTsKCiAgICAgICAgLypTeXN0ZW0ub3V0LnByaW50bG4oKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8bWF4U2l6ZSA7IGkrKykgewogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50KHNlZ1RyZWVbaV0uQisiICIpOwogICAgICAgIH0qLwoKICAgICAgICBSZWFkZXIgcyA9IG5ldyBSZWFkZXIoKTsKICAgICAgICBpbnQgTSA9IHMubmV4dEludCgpOwogICAgICAgIHdoaWxlIChNLS0gPiAwKSB7CiAgICAgICAgICAgIE5vZGUgdGVtcD1vYmoucXVlcnkocy5uZXh0SW50KCkgLSAxLCBzLm5leHRJbnQoKSAtIDEsIDAsIGxlbi0gMSwgMCxzZWdUcmVlKTsKICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKHRlbXAuQik7CiAgICAgICAgfQogICAgfQogICAgdm9pZCBidWlsZFRyZWUoaW50IGlucHV0W10saW50IGxvdyxpbnQgaGlnaCxpbnQgcG9zLE5vZGUgc2VnVHJlZVtdKXsKICAgICAgICBpZihsb3c+aGlnaCkKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIGlmKGxvdz09aGlnaCl7CiAgICAgICAgICAgIE5vZGUgbmV3Tm9kZT1uZXcgTm9kZSgpOwogICAgICAgICAgICBuZXdOb2RlLkI9aW5wdXRbbG93XTsKICAgICAgICAgICAgbmV3Tm9kZS5MPWlucHV0W2xvd107CiAgICAgICAgICAgIG5ld05vZGUuUj1pbnB1dFtsb3ddOwogICAgICAgICAgICBuZXdOb2RlLlQ9aW5wdXRbbG93XTsKICAgICAgICAgICAgc2VnVHJlZVtwb3NdPW5ld05vZGU7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgR1NTMU5PREUgb2JqPW5ldyBHU1MxTk9ERSgpOwogICAgICAgIGludCBtaWQ9KGxvdytoaWdoKS8yOwogICAgICAgIGludCBsZWZ0PXBvcyoyKzEscmlnaHQ9cG9zKjIrMjsKICAgICAgICBidWlsZFRyZWUoaW5wdXQsbG93LG1pZCxsZWZ0LHNlZ1RyZWUpOwogICAgICAgIGJ1aWxkVHJlZShpbnB1dCxtaWQrMSxoaWdoLHJpZ2h0LHNlZ1RyZWUpOwogICAgICAgIHNlZ1RyZWVbcG9zXT1vYmouam9pbihzZWdUcmVlW2xlZnRdLHNlZ1RyZWVbcmlnaHRdKTsKICAgIH0KCiAgICBOb2RlIGpvaW4oTm9kZSBsZWZ0LE5vZGUgcmlnaHQpewogICAgICAgIEdTUzFOT0RFIG9iaj1uZXcgR1NTMU5PREUoKTsKICAgICAgICBOb2RlIG5ld05vZGU9bmV3IE5vZGUoKTsKICAgICAgICBuZXdOb2RlLkw9TWF0aC5tYXgobGVmdC5MLGxlZnQuVCtyaWdodC5MKTsKICAgICAgICBuZXdOb2RlLlI9TWF0aC5tYXgobGVmdC5SK3JpZ2h0LlQscmlnaHQuUik7CiAgICAgICAgbmV3Tm9kZS5UPWxlZnQuVCtyaWdodC5UOwogICAgICAgIG5ld05vZGUuQj1vYmoubWF4MyhsZWZ0LkIscmlnaHQuQixsZWZ0LlIrcmlnaHQuTCk7CiAgICAgICAgcmV0dXJuIG5ld05vZGU7CiAgICB9CiAgICBOb2RlIHF1ZXJ5KGludCBxbG93LGludCBxaGlnaCxpbnQgbG93LGludCBoaWdoLGludCBwb3MsTm9kZSBzZWdUcmVlW10pewogICAgICAgIC8vbm8gb3ZlcmxhcAogICAgICAgIGlmKHFsb3c+aGlnaCB8fCBsb3c+cWhpZ2gpewogICAgICAgICAgICByZXR1cm4gbmV3IE5vZGUoKTsKICAgICAgICB9CgogICAgICAgIC8vdG90YWwgb3ZlcmxhcAogICAgICAgIGlmKGxvdz49cWxvdyAmJiBoaWdoPD1xaGlnaCkKICAgICAgICAgICAgcmV0dXJuIHNlZ1RyZWVbcG9zXTsKCiAgICAgICAgLy9wYXJ0aWFsIG92ZXJsYXAKICAgICAgICBHU1MxTk9ERSBvYmo9bmV3IEdTUzFOT0RFKCk7CiAgICAgICAgaW50IG1pZD0obG93K2hpZ2gpLzI7CiAgICAgICAgaW50IGxlZnQ9cG9zKjIrMSxyaWdodD1wb3MqMisyOwogICAgICAgIHJldHVybiBvYmouam9pbihxdWVyeShxbG93LHFoaWdoLGxvdyxtaWQsbGVmdCxzZWdUcmVlKSxxdWVyeShxbG93LHFoaWdoLG1pZCsxLGhpZ2gscmlnaHQsc2VnVHJlZSkpOwogICAgfQogICAgaW50IG1heDMoaW50IGEsaW50IGIsaW50IGMpewogICAgICAgIHJldHVybiBNYXRoLm1heChhLE1hdGgubWF4KGIsYykpOwogICAgfQogICAgY2xhc3MgTm9kZXsKICAgICAgICBpbnQgTCxSLFQsQjsKICAgICAgICBOb2RlKCl7CiAgICAgICAgICAgIEw9LTE1MDA4OwogICAgICAgICAgICBSPS0xNTAwODsKICAgICAgICAgICAgVD0tMTUwMDg7CiAgICAgICAgICAgIEI9LTE1MDA4OwogICAgICAgIH0KICAgIH0KICAgIHN0YXRpYyBjbGFzcyBSZWFkZXIKICAgIHsKICAgICAgICBmaW5hbCBwcml2YXRlIGludCBCVUZGRVJfU0laRSA9IDEgPDwgMTY7CiAgICAgICAgcHJpdmF0ZSBEYXRhSW5wdXRTdHJlYW0gZGluOwogICAgICAgIHByaXZhdGUgYnl0ZVtdIGJ1ZmZlcjsKICAgICAgICBwcml2YXRlIGludCBidWZmZXJQb2ludGVyLCBieXRlc1JlYWQ7CgogICAgICAgIHB1YmxpYyBSZWFkZXIoKQogICAgICAgIHsKICAgICAgICAgICAgZGluID0gbmV3IERhdGFJbnB1dFN0cmVhbShTeXN0ZW0uaW4pOwogICAgICAgICAgICBidWZmZXIgPSBuZXcgYnl0ZVtCVUZGRVJfU0laRV07CiAgICAgICAgICAgIGJ1ZmZlclBvaW50ZXIgPSBieXRlc1JlYWQgPSAwOwogICAgICAgIH0KCiAgICAgICAgcHVibGljIFN0cmluZyByZWFkTGluZSgpIHRocm93cyBJT0V4Y2VwdGlvbgogICAgICAgIHsKICAgICAgICAgICAgYnl0ZVtdIGJ1ZiA9IG5ldyBieXRlWzY0XTsgLy8gbGluZSBsZW5ndGgKICAgICAgICAgICAgaW50IGNudCA9IDAsIGM7CiAgICAgICAgICAgIHdoaWxlICgoYyA9IHJlYWQoKSkgIT0gLTEpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChjID09ICdcbicpCiAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICBidWZbY250KytdID0gKGJ5dGUpIGM7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuIG5ldyBTdHJpbmcoYnVmLCAwLCBjbnQpOwogICAgICAgIH0KCiAgICAgICAgcHVibGljIGludCBuZXh0SW50KCkgdGhyb3dzIElPRXhjZXB0aW9uCiAgICAgICAgewogICAgICAgICAgICBpbnQgcmV0ID0gMDsKICAgICAgICAgICAgYnl0ZSBjID0gcmVhZCgpOwogICAgICAgICAgICB3aGlsZSAoYyA8PSAnICcpCiAgICAgICAgICAgICAgICBjID0gcmVhZCgpOwogICAgICAgICAgICBib29sZWFuIG5lZyA9IChjID09ICctJyk7CiAgICAgICAgICAgIGlmIChuZWcpCiAgICAgICAgICAgICAgICBjID0gcmVhZCgpOwogICAgICAgICAgICBkbwogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICByZXQgPSByZXQgKiAxMCArIGMgLSAnMCc7CiAgICAgICAgICAgIH0gIHdoaWxlICgoYyA9IHJlYWQoKSkgPj0gJzAnICYmIGMgPD0gJzknKTsKCiAgICAgICAgICAgIGlmIChuZWcpCiAgICAgICAgICAgICAgICByZXR1cm4gLXJldDsKICAgICAgICAgICAgcmV0dXJuIHJldDsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgdm9pZCBmaWxsQnVmZmVyKCkgdGhyb3dzIElPRXhjZXB0aW9uCiAgICAgICAgewogICAgICAgICAgICBieXRlc1JlYWQgPSBkaW4ucmVhZChidWZmZXIsIGJ1ZmZlclBvaW50ZXIgPSAwLCBCVUZGRVJfU0laRSk7CiAgICAgICAgICAgIGlmIChieXRlc1JlYWQgPT0gLTEpCiAgICAgICAgICAgICAgICBidWZmZXJbMF0gPSAtMTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgYnl0ZSByZWFkKCkgdGhyb3dzIElPRXhjZXB0aW9uCiAgICAgICAgewogICAgICAgICAgICBpZiAoYnVmZmVyUG9pbnRlciA9PSBieXRlc1JlYWQpCiAgICAgICAgICAgICAgICBmaWxsQnVmZmVyKCk7CiAgICAgICAgICAgIHJldHVybiBidWZmZXJbYnVmZmVyUG9pbnRlcisrXTsKICAgICAgICB9CiAgICB9Cn0K