Задана послідовність цілих чисел a1, a2, ..., an (|ai| ≤ 15007, 1 ≤ n ≤ 50000). Запит має вигляд:

Query(x, y) = MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}

Вам необхідно вивести відповіді на задані m запитів.

Вхідні дані

Перший рядок містить значення n. У другому рядку задано n цілих чисел послідовності. Третій рядок містить кількість запитів m. Далі йдуть m рядків, причому i-ий рядок містить два числа xi та yi.

Вихідні дані

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