Чи можете Ви відповісти на ці питання - 1

Задана послідовність цілих чисел 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}

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

Вхідні дані

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

Вихідні дані

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

Приклади