406847: GYM102569 L The Dragon Land

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. The Dragon Landtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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

Output one integer — the maximal hero's profit.

ExamplesInput
5
8 2 4 9 1
Output
15
Input
2
1 1
Output
0

加入题单

上一题 下一题 算法标签: