该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

选拔牌神需要N张扑克牌。这N张扑克牌呈一个序列铺在桌子上，每张扑克牌上都写着\([1,500]\)中的一些数字（当然，这些数字是看不到的）。每当你选择其中的一张牌，与这张牌相邻的两张牌上的数字会与你选择的牌上的数字相乘，加入你的得分（初始得分为0），一直下去……最后剩下序列两端的牌。得分最小的会获得“牌神”的称号。

Description

为了成为“牌神”，你已经预先知道了每张牌上的数字。你要在1秒内计算出最小的得分。

Format

Input

第一行一个整数N

第二行N个数字，表示每张牌上的数字

Output

一行，最小的得分

Sample 1

Input

6
10 1 50 50 20 5

Output

3650

Limitation

\(1 \le N \le 400\)

Source

AOGC Original