Cho dãy số \(a_1,a_2,..., a_n\) (\(|a_i| \leq 15000 ,n \leq 50000\)). Với 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.

Ví dụ

Input

3
-1 2 3
1
1 2

Output

2