Задана последовательность целых чисел a1, a2, ..., an (|ai| ≤ 15007, 1 ≤ n ≤ 50000). Запрос имеет вид:

Query(x, y) = MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}

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

Входные данные

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

Выходные данные

Вывести ответы на m запросов, по одному ответу в строке.