在一个战斗场景中，有 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 的勇气值。