Задано послідовність цілих чисел \(a_1, a_2, ..., a_n\) \((|a_i| ≤ 15007\), \(1 ≤ n ≤ 50000)\). Запит має вигляд:

Query(x, y) = MAX {\(a_i + a_i+1 + ... + a_j\), \(x ≤ i ≤ j ≤ y\)}

(тобто на відрізку \(x..y\) знайти неперервний підмасив з максимальною сумою)

Вам необхідно вивести відповіді на задані \(m\) запитів. (\(1 \le m \le 500500\))

Формат вхідних даних

Перший рядок містить значення \(n\).

У другому рядку задані \(n\) цілих чисел послідовності.

Третій рядок містить кількість запитів \(m\).

Далі слідує \(m\) рядків, причому \(i\)-й рядок містить два числа \(x_i\) та \(y_i\).

Формат вихідних даних

Вивести відповіді на \(m\) запитів, по одній відповіді у рядку.

Приклад вхідних даних

3 
-1 2 3
2
1 2
2 3

Приклад вихідних даних

2
5