Cho dãy số a[1],a[2],...,a[n] (\(|a[i]| \leq 15000 ,n \leq 50000\)).

Hàm q(x,y)=maxtổng(\(a[i]+a[i+1]+...+a[j]\)), \(x \leq i \leq j \leq y\).

Cho \(m\) câu hỏi dạng \(x,y\) (\(1 \leq x \leq y \leq n\)). (\(m \leq 50000\)).

Hãy tính các \(q(x,y)\).

Input

• Dòng đầu là n
• Dòng thứ 2 là dãy \(A\)
• Dòng thứ 3 là m.
• \(m\) dòng tiếp theo mỗi dòng là \(1\) cặp số \(x,y\).

Output

• Lần lượt ghi ra các \(q(x,y)\) tương ứng. Mỗi kết quả ghi trên 1 dòng.

Example

3
-1 2 3
1
1 2

2