Bạn được cho một dãy số \(a_1, a_2, \dots, a_n\) và \(m\) truy vấn. Mỗi truy vấn gồm hai số \(l\) và \(r\) (\(1 \le l \le r \le n\)). Với mỗi truy vấn, bạn cần in ra tổng lớn nhất của một dãy con liên tiếp nằm trong đoạn từ \(l\) tới \(r\).

Cụ thể, với mỗi truy vấn \((l, r)\), bạn cần tìm giá trị lớn nhất của \(\sum_{k=i}^{j} a_k\) sao cho \(l \le i \le j \le r\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 15000\)) là số phần tử của dãy \(a\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 15000\)).
• Dòng thứ ba chứa số nguyên \(m\) (\(1 \le m \le 15000\)) là số lượng truy vấn.
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) (\(1 \le l \le r \le n\)).

Output

• In ra \(m\) dòng, mỗi dòng là câu trả lời cho một truy vấn tương ứng.

Example

6
2 3 -6 4 5 1
4
1 2
1 4
2 6
3 6

5
5
10
10

Constraints

• \(1 \le n \le 15000\)
• \(|a_i| \le 15000\)
• \(1 \le m \le 15000\)
• \(1 \le l \le r \le n\)