7396: GSS1 - Can you answer these queries I
[Creator : ]
Description
You are given a sequence A[1], A[2], ..., A[N] . ( $|A[i]| ≤ 15,007 , 1 ≤ N ≤ 500,000$). A query is defined as follows:
Query(x,y) = Max {a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.
Given $M$ queries, your program must output the results of these queries.
Query(x,y) = Max {a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.
Given $M$ queries, your program must output the results of these queries.
Input
The first line of the input file contains the integer $N$.
In the second line, $N$ numbers follow.
The third line contains the integer $M$.
$M$ lines follow, where line $i$ contains two numbers $x_i$ and $y_i$.
In the second line, $N$ numbers follow.
The third line contains the integer $M$.
$M$ lines follow, where line $i$ contains two numbers $x_i$ and $y_i$.
Output
Your program should output the results of the $M$ queries, one query per line.
Sample 1 Input
3
-1 2 3
1
1 2
Sample 1 Output
2