eolymp
bolt
Try our new interface for solving problems
Problems

Can you answer these queries - 1

Can you answer these queries - 1

Time limit 1 second
Memory limit 128 MiB

You are given an integer sequence a[1], a[2], ..., a[n] (|a[i]| ≤ 15007 , 1n50000). A query is defined as follows:

Query(x, y) = MAX {a[i] + a[i+1] + ... + a[j], xijy}

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

Input data

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].

Output data

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

Examples

Input example #1
3 
-1 2 3
1
1 2
Output example #1
2