P1021推翻暴政（revolt）

【题目背景】

古道重新显现后，tfbz 集结了反抗萨米旧都的同伴。为了避开守卫，他们必须从城外的渡口尽快渡河，潜入旧都。

【题目描述】

共有 $n$ 名同伴按照编号 $1\sim n$ 依次来到渡口，保证 $n$ 为奇数。第 $i$ 名同伴独自渡河需要 $a_i$ 单位时间。

渡口位于旧都守卫视线之外，却十分狭窄，同伴们只能按照事先约定的顺序分批赶到。tfbz 无法改变他们的到达顺序，只能决定每次由谁先乘船离开。

最初，渡口中只有第 $1$ 名同伴。此后，每当轮到下一批同伴抵达，tfbz 必须按照以下过程作出选择：

• 每次有接下来的两名同伴同时到达渡口；
• 此时渡口中恰好有三名同伴；
• 必须从中选择两名同伴共同乘船渡河；
• 若选择第 $i,j$ 名同伴共同渡河，需要花费 $\max(a_i,a_j)$ 单位时间；
• 没有被选择的那名同伴继续留在渡口，等待下一批两名同伴。

共同渡河的两名同伴会直接抵达对岸，不再回到渡口；留下的一人则会与下一批到达的两名同伴再次组成三人。这个过程一直重复，直到所有同伴都已经到达。

此时，渡口中只会剩下一名同伴。他需要独自渡河，花费 $a_i$ 单位时间。

只要所有人都抵达对岸，tfbz 就能带领他们潜入萨米旧都，正式开始推翻暴政的行动。他想知道，怎样安排每次共同渡河的两名同伴，才能使所有人渡河所需的总时间最少。

【输入格式】

从文件 $\textbf{\textit{revolt.in}}$ 中读入数据。

第一行一个正奇数 $n$，表示参与行动的同伴数量。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 名同伴独自乘船渡河所需的时间。

【输出格式】

输出到文件 $\textbf{\textit{revolt.out}}$ 中。

输出一行一个整数，表示所有同伴全部渡过河流所需的最少总时间。

【样例 1 输入】

1524 2 7 3 6

【样例 1 输出】

114

【说明/提示】

【样例 1 解释】

最初，编号为 $1,2,3$ 的同伴位于渡口。可以选择第 $1,2$ 名同伴共同渡河，花费 $\max(4,2)=4$ 单位时间，此时第 $3$ 名同伴继续留在渡口。

随后第 $4,5$ 名同伴同时到达。选择第 $3,5$ 名同伴共同渡河，花费 $\max(7,6)=7$ 单位时间，留下第 $4$ 名同伴。最后，第 $4$ 名同伴独自渡河，花费 $3$ 单位时间。

总时间为 $4+7+3=14$。可以证明不存在总时间更少的渡河方案。

【样例 2】

见选手目录下的 $\textbf{\textit{revolt/revolt2.in}}$ 和 $\textbf{\textit{revolt/revolt2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{revolt/revolt3.in}}$ 和 $\textbf{\textit{revolt/revolt3.ans}}$。

该组样例符合测试点 $5\sim 9$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{revolt/revolt4.in}}$ 和 $\textbf{\textit{revolt/revolt4.ans}}$。

该组样例符合测试点 $10\sim 14$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{revolt/revolt5.in}}$ 和 $\textbf{\textit{revolt/revolt5.ans}}$。

该组样例符合测试点 $15\sim 19$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{revolt/revolt6.in}}$ 和 $\textbf{\textit{revolt/revolt6.ans}}$。

该组样例符合测试点 $20\sim 25$ 的数据范围。

【数据范围】

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

特殊性质 A：满足 $a_1\leq a_2\leq\cdots\leq a_n$。

特殊性质 B：序列 $a$ 中至多有 $100$ 种不同的数值。