Задана последовательность целых чисел 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 запросов, по одному ответу в строке.