F. Dogecoin
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В последнее время криптовалюты становятся все более популярными. Аня решила, что самое время начать майнинг криптовалюты Dogecoin. Компьютер у Ани не очень мощный, поэтому Аня добывает ровно $$$1$$$ Dogecoin в день. В интернете есть прогнозы стоимости $$$1$$$ Dogecoin на ближайшие $$$n$$$ дней. Каждый день Аня может продать любое количество Dogecoin, которое у нее сейчас есть. Обратите внимание, что если Аня добыла dogecoin в $$$i$$$-й день, то она может продать его в тот же день.

Аня еще не решила, когда начинать майнинг. Она подготовила $$$q$$$ возможных планов и для каждого из них хочет знать максимальную прибыль, которую она может получить. Каждый из планов описывается двумя числами $$$l$$$ и $$$r$$$ — первый и последний дни майнинга. Обратите внимание, что после $$$r$$$-го дня у Ани не должно остаться ни одного Dogecoin.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^6$$$), где $$$c_i$$$ — стоимость Dogecoin в $$$i$$$-й день.

Третья строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество планов Ани.

Следующие $$$q$$$ строк содержат по два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — первый и последний дни майнинга.

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

Для каждого плана Ани выведите одно целое число — максимальную прибыль, которую она может получить, используя этот план.

Пример
Входные данные
5
4 1 2 3 2
4
1 5
2 4
3 5
5 5
Выходные данные
15 9 8 2