В последнее время криптовалюты становятся все более популярными. Аня решила, что самое время начать майнинг криптовалюты 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
| Kotlin Heroes: Episode 6 |
|---|
| Закончено |
