В последнее время криптовалюты становятся все более популярными. Аня решила, что самое время начать майнинг криптовалюты Dogecoin. Компьютер у Ани не очень мощный, поэтому Аня добывает ровно \(1\) Dogecoin в день. В интернете есть прогнозы стоимости \(1\) Dogecoin на ближайшие \(n\) дней. Каждый день Аня может продать любое количество Dogecoin, которое у нее сейчас есть. Обратите внимание, что если Аня добыла dogecoin в \(i\)-й день, то она может продать его в тот же день.
Аня еще не решила, когда начинать майнинг. Она подготовила \(q\) возможных планов и для каждого из них хочет знать максимальную прибыль, которую она может получить. Каждый из планов описывается двумя числами \(l\) и \(r\) — первый и последний дни майнинга. Обратите внимание, что после \(r\)-го дня у Ани не должно остаться ни одного Dogecoin.
Выходные данные
Для каждого плана Ани выведите одно целое число — максимальную прибыль, которую она может получить, используя этот план.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 1 2 3 2
4
1 5
2 4
3 5
5 5
|
15 9 8 2
|