e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

ADA University - March 7 - Segment Tree

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

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

Query(x, y) = MAX {ai + ai+1 + ... + aj, xijy}

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

Вхідні дані

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

Вихідні дані

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

Ліміт часу 1 секунди
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 
-1 2 3
1
1 2
Вихідні дані #1
2