e-olymp
Problems

Can you answer these queries - 1

Can you answer these queries - 1

You are given an integer sequence a1, a2, ..., an (|ai| ≤ 15007 , 1n50000). A query is defined as follows:

Query(x, y) = MAX {ai + ai+1 + ... + aj, xijy}

Given m queries, your program must output the results of these queries.

Input

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 xi and yi.

Output

Print the results of the m queries, one query per line.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
3 
-1 2 3
1
1 2
Output example #1
2