eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Задана послідовність цілих чисел a[1], a[2], ..., a[n] (|a[i]| ≤ 15007, 1n50000). Запит має вигляд:

Query(x, y) = MAX {a[i] + a[i+1] + ... + a[j], xijy}

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
3 
-1 2 3
1
1 2
Вихідні дані #1
2