在矩阵运算中，矩阵的乘法满足结合律，即 (A × B) × C = A × (B × C)，但矩阵乘法不满足交换律，即 A × B ≠ B × A。

假设给定 N 个矩阵，依次编号为 1 到 N，第 i 个矩阵的维度为 p[i-1] × p[i]。矩阵的乘法运算代价为矩阵的行数 × 列数 × 共同维度。例如，如果矩阵 A 的大小是 10 × 30，矩阵 B 的大小是 30 × 5，那么 A × B 的计算代价为 10 × 30 × 5 = 1500。

我们的目标是找到一种最优的括号化方案，使得 N 个矩阵依次相乘的总计算代价最小。

• 第一行包含一个整数 N（2 ≤ N ≤ 100），表示矩阵的个数。
• 第二行包含 N+1 个整数 p[0], p[1], ..., p[N]，表示 N 个矩阵的维度。其中，第 i 个矩阵的大小为 p[i-1] × p[i]。

• 输出一个整数，表示矩阵连乘的最小计算代价。

数据范围

• 2 ≤ N ≤ 100
• 1 ≤ p[i] ≤ 1000

区间dp