Description

给定正整数 $n$ 和正整数数组 $A_i(1\le i\le n)$，现有 $n$ 堆石子排成一列，第 $i$ 堆石子有 $A_i$ 个，其中对于任一正整数 $i(i<n)$ ，第 $i$ 堆石子与第 $i+1$ 堆石子相邻。每次将两堆石子合并成一堆，新堆的石子数是原来两堆石子数之和，代价是原来两堆石子数之积，求合并 $n-1$ 次将 $n$ 堆石子合并成一堆的代价和最小是多少。

Input Format

第一行，一个正整数 $n$。

第二行，$n$ 个正整数，第 $i$ 个正整数表示 $A_i$，相邻两个数之间有一个空格隔开。

Output Format

仅一行，一个正整数，表示答案。

Sample

输入样例：

2 
2 2

输出样例：

4

Hint

对于所有的测试点，满足 $n\le 30000,A_i\le 200000$。