[Baltic2007]序列问题Sequence

对于一个给定的序列 $a_1,\ldots,a_n$ ，可以进行如下操作：选择序列中相邻的两个元素 $a_i$ 和 $a_{i+1}$ ，用一个元素 $\max(a_i,a_{i+1})$ 替代它们，从而得到一个长度减少 $1$ 的新序列。该操作的代价为 $\max(a_i,a_{i+1})$ 。

经过 $n-1$ 次操作后，序列长度将变为 $1$ 。请计算将给定序列变为长度为 $1$ 的序列所需的最小总代价。

输入格式

第一行输入一个整数 $n$ ，表示给定序列的长度。

接下来 $n$ 行，每行输入一个整数 $a_i$ ，表示序列中的第 $i$ 个元素。

输出一行一个整数，表示将序列变为长度为 $1$ 的序列所需的最小总代价。

本题为 Baltic 2007 试题「序列问题 Sequence」，题面与测试数据整理自 BZOJ 1345。