Can you answer these queries I

Source: SPOJ

Version: Phuoc Hung OJ Extended

Given an array $A_1,A_2,\ldots,A_N$, each query $x,y$ asks for the maximum sum of a non-empty contiguous subarray fully contained in $[x,y]$:

Input

The first line contains $N$.

The second line contains the array.

The third line contains $Q$.

Each of the next $Q$ lines contains $x,y$.

Output

For each query, print the maximum contiguous subarray sum.

Subtasks

• Subtask 1 — 20%: $1\le N,Q\le 50$, $|A_i|\le 1000$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$, $|A_i|\le 15007$.
• Subtask 3 — 50%: $1\le N\le 50000$, $1\le Q\le 50000$, $|A_i|\le 15007$.

Examples

Input

3
-1 2 3
1
1 2

Output

2

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.