Can you answer these queries - 1

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.

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 x[i] and y[i].

Output

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

Examples