156. 勇敢牛牛战斗序列
内存限制：256 MB
时间限制：1.000 S
题目描述
在一个战斗场景中，有 n 个怪物，每个怪物的战斗力为 a[i]。起初，牛牛的战斗力为 0。牛牛需要与这 n 个怪物逐一战斗，牛牛可以自由选择与怪物的战斗顺序。设牛牛与第 i 个怪物战斗时的战斗力为 x，战斗规则如下：
- 如果 x < a[i]，牛牛触发被动技能“勇敢牛牛不怕困难”，战斗力提升至 a[i]，并战胜该怪物，同时勇气值增加 a[i] - x。
- 如果 x ≥ a[i]，牛牛直接战胜该怪物，并且战斗结束后，牛牛的战斗力降低至 a[i]。
牛牛的目标是选择合适的战斗顺序，以便在打败所有怪物后，累计获得的勇气值最大化。
输入
第一行输入一个整数 n（1 < n < 200000），表示怪物的数量。
第二行输入 n 个整数 a1, a2, ..., an（1 <= a[i] <= 10^9），表示每个怪物的战斗力。
输出
输出一个整数，表示牛牛可以获得的最大勇气值。
样例输入 复制
3
1 2 2样例输出 复制
3提示
牛牛可以按照以下顺序与怪物战斗，以获得最大的勇气值：
1. 首先，牛牛与编号为 2 的怪物战斗。当时牛牛的战斗力为 0，因此获得 a[2] - 0 = 2 的勇气值。战斗结束后，牛牛的战斗力提升至 2。
2. 接下来，牛牛与编号为 1 的怪物战斗，此时牛牛的战斗力为 2。牛牛无需触发技能，直接击败怪物，勇气值增加 0，战斗结束后，牛牛的战斗力降低至 1。
3. 最后，牛牛与编号为 3 的怪物战斗。牛牛的战斗力为 1，触发技能，获得 a[3] - 1 = 1 的勇气值，战斗结束后，牛牛的战斗力提升至 2。
通过这种顺序，牛牛累计获得 2 + 1 = 3 的勇气值。