У місті Є. відкрилось нове кафе "Хоботанія", розраховане на слоників. Усі клієнти приходять у кафе в момент часу 0, а господар вибирає у якому порядку їх обслуговувати. При цьому кожну секунду обслуговується один слоник (перший обслуговується у момент часу 0).
Господару відомо, що якщо слоника i буде обслужено у момент часу t, то він заплатить tips[i]
- t чайових. Якщо число tips[i]
- t від'ємне, то він нічого не платить.
Допоможіть господару знайти такий порядок обслуговування слоників, який принесе йому максимальний прибуток.
Перший рядок містить кількість слоників n (0 ≤ n ≤ 100), що прийшли у кафе. Наступний рядок містить n чисел tips[1]
, tips[2]
, ..., tips[n]
(0 ≤ tips[i]
≤ 10^5
).
Виведіть максимальний прибуток володаря кафе.