Migrated from Lutece 1940 心的距离

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

小a深爱着小c，但和小c的座位之间有n位吃瓜群众，小a想要赶走中间这n位吃瓜群众，从而和小c拉近心的距离。包括小a小c一共n+2个人（小a编号为1，小c编号为n+2），从左到右第i个人的吃瓜指数为$a_i$。赶走第i个人时，设第i个人左边第一个还没走的人编号为j，右边为k，需付出$a_j$*$a_i$*$a_k$颗瓜子。小a想要知道最少付出多少颗瓜子，可以赶走中间所有的吃瓜群众，这就需要你机智的安排顺序了。

Input

第一行一个整数 $n\ (1 \le n \le 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

每周一题 div2