406847: GYM102569 L The Dragon Land

A hero is going to make a journey through the dragon land. The dragon land is a road, and $$$n$$$ dragon lairs are situated along this road. The hero will follow this road, never turning back.

Passing by the dragon lair, it is possible to fight the dragon, kill him and get $$$a_i$$$ gold. But it is not always profitable to kill all the dragons, as the weapons and armor wear out: after the first battle the hero will have to spend 1 gold on repairing them, after the second battle — 2 gold, and so on, after the $$$k$$$-th battle he will have to spend $$$k$$$ gold.

Initially the hero has no gold. At any moment of his journey and after it the hero can't have negative amount of gold.

How much gold the hero can earn in the journey?

The first line contains the integer $$$n$$$ ($$$1 \le n \le 200000$$$) — the number of dragon lairs.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — amounts of gold the hero can earn fighting the $$$i$$$-th dragon.

Output one integer — the maximal hero's profit.

5
8 2 4 9 1

15

2
1 1

0