Герой собирается совершить путешествие через страну драконов. Страна драконов представляет собой дорогу, вдоль которой расположены $$$n$$$ логов драконов. Герой будет двигаться по этой дороге, никогда не разворачиваясь назад.
Проходя мимо очередного логова дракона, можно подраться с драконом, убить его и получить за это $$$a_i$$$ золота. Но убивать всех драконов подряд невыгодно, так как оружие и доспехи изнашиваются: после первой битвы придется потратить 1 единицу золота на их ремонт, после второй битвы — 2 единицы золота, и так далее, после $$$k$$$-й битвы придется потратить $$$k$$$ единиц золота.
Изначально у героя 0 золота. На протяжении всего путешествия и после его окончания у героя не может быть отрицательного количества золота.
Какое максимальное количество золота герой сможет заработать за это путешествие?
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 200000$$$) — количество логов драконов.
Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — количество золота, которое можно заработать в битве с $$$i$$$-м драконом.
Выведите единственное целое число — максимально возможную прибыль героя.
5 8 2 4 9 1
15
2 1 1
0
