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

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

1 секунда
128 мегабайтів
Легка

Вам дано послідовність цілих чисел a_1, a_2, \ldots, a_n (|a_i| \leq 15007, 1 \leq n \leq 50000). Запит визначається так:

\text{Запит}(x, y) = \max \{ a_i + a_{i+1} + \cdots + a_j \mid x \leq i \leq j \leq y \}

Потрібно відповісти на таких запитів.

Вхідні дані

У першому рядку задано ціле число . У другому рядку — послідовність із цілих чисел. У третьому рядку подано ціле число . Кожен із наступних рядків містить по два цілих числа x_i та y_i.

Вихідні дані

Виведіть відповідь на кожен запит у окремому рядку.

Приклади

Приклад 1

Loading
Loading