В последнее время криптовалюты становятся все более популярными. Аня решила, что самое время начать майнинг криптовалюты 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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач