P6196 [EER1] Cost

> Personal experiences and the twists of fate forced me to grow up. The cost of all this should become the strength to live on in the future. — Sanmao Xiao Z likes playing number games.

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.

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 one positive integer in one line, which is the minimum total cost.

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