Migrated from Lutece 2039 心的距离

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

通过坡道上的交谈，子辉知道了她叫Sakura，如樱花一样美丽的名字。而且还是同一个班上的。但在子辉与Sakura的班级座位之间却隔着有$n$位同学，子辉想要支走中间这$n$位同学，从而和Sakura拉近心的距离。包括子辉和Sakura在内一共$n+2$个人（子辉编号为$1$，Sakura编号为$n+2$），从左到右第$i$个人的任性指数为$a_i$。支走第$i$个人时，设第$i$个人左边最近的还没走的人（可以是子辉或Sakura）编号为$j$，右边为$k$，需付出$a_j \times a_i \times a_k$ 的精力。子辉想要知道最少付出多少精力，可以支走中间所有的同学，拉近与Sakura的距离，这就需要机智地安排顺序了。

Input

第一行一个整数 $n$ ($1≤n≤200$). 第二行 $n+2$ 个用空格分隔的整数 $a_1$,$a_2$,...,$a_{n+2}$， 保证 $1 \le a_i \le 100$.

Output

输出最少需要付出的精力

Samples

2
10 100 5 50

7500

Resources

2018 UESTC Training for Dynamic Programming