You are given an integer sequence a[1]
, a[2]
, ..., a[n]
(|a[i]
| ≤ 15007 , 1 ≤ n ≤ 50000). 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.
The first line contains the integer n. In the second line n integers of the sequence are given. The third line contains the integer m. Then m lines follow, where line i contains two numbers x[i]
and y[i]
.
Print the results of the m queries, one query per line.