矩陣乘法必須滿足 A 的行數等於 B 的列數，若 A 是 \(p \times q\) 的矩陣，B 是 \(q \times r\) 的矩陣，則 \(A \times B\) 的結果是一個 \(p \times r\) 的矩陣，而需要的純量乘法數為 \(p \cdot q \cdot r\)。

矩陣乘法滿足結合律，也就是說 \(A \times B \times C = (A \times B) \times C = A \times (B \times C)\)，可是不同順序所需要的純量乘法數會不同。

輸入 \(p[0], p[1], \dots, p[n]\)，代表有 \(n\) 個矩陣相乘的乘法鏈，而它們的矩陣大小依序為 \(p[0] \times p[1], p[1] \times p[2], \dots, p[n-1] \times p[n]\)。請找出最佳的相乘順序，使得使用的純量乘法數總和最少。

例子

若 \(n = 3\)，矩陣大小為：

• \(A_1: 3 \times 5\)
• \(A_2: 5 \times 4\)
• \(A_3: 4 \times 2\)

1. 乘法順序 \((A_1 \times A_2) \times A_3\)：

   • 乘法數：\(3 \cdot 5 \cdot 4 + 3 \cdot 4 \cdot 2 = 84\)

2. 乘法順序 \(A_1 \times (A_2 \times A_3)\)：

   • 乘法數：\(3 \cdot 5 \cdot 2 + 5 \cdot 4 \cdot 2 = 70\)

最少的純量乘法數為 \(70\)。

輸入格式

第一行是正整數 n。 第二行有 n+1 個正整數， p[0] ~ p[n]，數字間以空白隔開。 n <= 200，p[i] <= 200

輸出格式

最小的純量乘法數量。

範例輸入 1

3
3 5 4 2

範例輸出 1

70

範例輸入 2

4
5 1 3 4 2

範例輸出 2

30