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

Query(x, y) = MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}

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.