Background

Personal ordeals and the vicissitudes of fate have forced me to mature. All these costs are the strength for me to live on in the future.
—— San Mao

Xiao Z enjoys playing with numbers.

Problem Description

Given a sequence of length $n+2$, denoted as $a_i$, where the first and the $(n+2)$-th numbers are fixed as $1$. You can choose a number in the middle of the sequence (not the first or the last) to delete, and the cost of deleting the number at position $p$ is $a_{p-1} \times a_p \times a_{p+1}$. You need to perform this operation until no more operations can be performed. Find the minimum total cost.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers, where the $i$-th number represents $a_{i+1}$.

Output Format

A single line containing a positive integer, representing the minimum total cost.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

9

Sample Input #2

4
19 26 8 17

Sample Output #2

846

Sample Input #3

6
1 1 1 1 1 1

Sample Output #3

6

Notes

Explanation of Sample #1:

First, delete $3$, the cost is $6$, then delete $2$, the cost is $2$, and finally delete $1$, the cost is $1$.

The total cost is $6 + 2 + 1 = 9$.

This problem uses batched testing.

For $100\%$ of the test cases: $1 \leq n \leq 10^6$, $1 \leq a_i \leq 10^4$.

This problem consists of $6$ sub-tasks, each with its own score and constraints:

Sub-task $1$ ($1$ point): $a_i = 1$.

Sub-task $2$ ($14$ points): $1 \leq n \leq 10$.

Sub-task $3$ ($5$ points): $1 \leq a_i \leq 2$.

Sub-task $4$ ($14$ points): $1 \leq n \leq 40$.

Sub-task $5$ ($26$ points): $1 \leq n \leq 500$.

Sub-task $6$ ($40$ points): No special restrictions.

Special Thanks

Idea: smrsky

Solution: CYJian

Data: iostream

见题面 Input 部分

见题面 Output 部分