Description

You are given a sequence $a_i$ of length $n+2$, where the $1$st number and the $(n+2)$nd number are fixed as $1$. Each time, you may choose a number in the middle of the sequence and delete it (it cannot be the first or the last). 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 are possible. 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

Output one positive integer in one line, which is the minimum total cost.

3
1 2 3

9

4
19 26 8 17

846

6
1 1 1 1 1 1

6

Hint

Explanation for Sample 1:

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

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

This problem uses bundled testdata.

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

This problem has $6$ subtasks. The score and constraints for each subtask are as follows:

Subtask $1$ ($1$ point): $a_i = 1$.

Subtask $2$ ($14$ points): $1 \leq n \leq 10$.

Subtask $3$ ($5$ points): $1 \leq a_i \leq 2$.

Subtask $4$ ($14$ points): $1 \leq n \leq 40$.

Subtask $5$ ($26$ points): $1 \leq n \leq 500$.

Subtask $6$ ($40$ points): no special constraints.

Special Thanks

idea: smrsky

solu: CYJian

data: iostream

Translated by ChatGPT 5