L - The Dragon Land

SDUT 2022 Spring Individual Contest(for 21) - 6 - Virtual Judge

A hero is going to make a journey through the dragon land. The dragon land is a road, and nn 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_iai​ 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 kk-th battle he will have to spend kk 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 nn (1 le n le 2000001≤n≤200000) — the number of dragon lairs.

The second line contains nn integers a_iai​ (1 le a_i le 10^91≤ai​≤109) — amounts of gold the hero can earn fighting the ii-th dragon.

Output

Output one integer — the maximal hero's profit.

Sample 1

5
8 2 4 9 1

15

Sample 2

2
1 1

0

题意： 一个英雄要去龙的土地上旅行。龙地是一条路，沿着这条路有许多龙的巢穴。英雄会沿着这条路，永不回头。
路过龙穴，有可能与龙搏斗，杀死他并获得ai金。但它并不总是有利可图，杀死所有的龙、武器和盔甲磨损。在第一次战斗英雄将不得不花1黄金修复它们,在第二次战役花2黄金,k的战斗后,他将不得不花k黄金。
一开始英雄没有金子。在他的旅程的任何时刻，在此之后，英雄不可能拥有负数量的金币。
英雄在旅途中可以获得多少金币?
 

#include
using namespace std;
int n;
int a[500005];
int flag=1;
cmp(int x,int y)
{
    return x>y;
}
int main()
{
    scanf("%d",&n);
    long long sum=0,t=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1; i<=n; i++)
    {

        if(a[i]-flag>=0)
        {
            t=t+a[i]-flag;
            flag++;
        }
        else
            break;
    }

    printf("%lld",t);
}