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