题目描述

小杨在班级里组织一个圆圈游戏。一共有 $n$ 位同学参加，第 $i$ 位同学的友好值为 $a_i$。

游戏规则如下：

• 同学们依次加入一个圆圈，小杨可以任意决定每位同学加入的顺序；
• 当一位同学加入时，他会被安排在圆圈上两位已经相邻的同学之间，此时他的「舒适度」等于这两位同学友好值中的较小值；
• 第一位加入的同学在圆圈上还没有相邻的同学，他的舒适度为 $0$。

小杨希望所有同学的舒适度之和尽可能大。请你帮他计算这个最大值。

输入格式

输入共两行。

第一行为一个整数 $n$，表示同学人数。

第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每位同学的友好值。

输出格式

输出一个整数，表示所有同学舒适度之和的最大值。

样例

4
2 2 1 3

7

3
5 5 5

10

样例解释

样例 1 中，友好值分别为 $3, 2, 2, 1$。一种最优安排是：友好值 $3$ 的同学先加入（舒适度 $0$）；友好值 $2$ 的同学加入，安排在 $3$ 的两侧之间，舒适度为 $\min(3, 3) = 3$；另一位友好值 $2$ 的同学加入，安排在 $3$ 与 $2$ 之间，舒适度为 $\min(3, 2) = 2$；友好值 $1$ 的同学加入，安排在两位友好值 $2$ 的同学之间，舒适度为 $\min(2, 2) = 2$。总舒适度为 $0 + 3 + 2 + 2 = 7$。

样例 2 中，三位同学友好值都为 $5$：第一位舒适度为 $0$，后两位的舒适度都为 $\min(5, 5) = 5$，总和为 $0 + 5 + 5 = 10$。

数据范围与约定

对于 $100\%$ 的数据，保证 $2 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 10^9$。

注意：答案可能超过 $2^{31} - 1$，请使用 long long（64 位整数）存储答案。