수열 줄이기

수열 $a_1, a_2, \dots, a_n$이 주어진다. 연산 $\text{reduce}(i)$는 인접한 두 원소 $a_i$와 $a_{i+1}$을 하나로 합쳐 그 자리에 $\max(a_i, a_{i+1})$를 놓는 연산이다. 이 연산을 한 번 수행할 때마다 수열의 길이는 $1$만큼 줄어든다.

$\text{reduce}$ 연산 한 번의 비용은 합쳐지는 두 원소의 최댓값 $\max(a_i, a_{i+1})$이다. 길이가 $n$인 수열에 이 연산을 $n-1$번 수행하면 수열의 길이는 $1$이 된다.

수열의 길이를 $1$로 만들 때까지 수행한 모든 $\text{reduce}$ 연산의 비용의 합의 최솟값을 구하여라.

첫째 줄에 수열의 길이 $n$ $(1 \le n \le 1{,}000{,}000)$이 주어진다. 이어지는 $n$개의 줄에 수열의 원소 $a_i$가 순서대로 하나씩 주어진다 $(0 \le a_i \le 1{,}000{,}000{,}000)$.

수열의 길이를 $1$로 만드는 데 드는 비용의 합의 최솟값을 첫째 줄에 출력한다.