Truy vấn tổng đoạn con lớn nhất I (Can you answer these queries I)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Cho dãy $A_1,A_2,\ldots,A_N$. Mỗi truy vấn cho $x,y$ và yêu cầu tìm tổng lớn nhất của một đoạn con liên tiếp, không rỗng, nằm hoàn toàn trong $[x,y]$:

Input

Dòng đầu chứa $N$.

Dòng thứ hai chứa $N$ số nguyên của dãy.

Dòng thứ ba chứa $Q$.

$Q$ dòng tiếp theo, mỗi dòng chứa $x,y$.

Output

Với mỗi truy vấn, in tổng đoạn con liên tiếp lớn nhất.

Subtask

• 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$.

Ví dụ

Input

3
-1 2 3
1
1 2

Output

2

Giải thích

Trong đoạn $[1,2]$ gồm $[-1,2]$, đoạn con không rỗng có tổng lớn nhất chỉ gồm phần tử $2$.