靶场上有 n 块靶排成一排，从左到右依次编号为 1, 2, 3, \ldots, n，且每块靶上都标有一个整数。 当某块靶被击中后，击中者会得到 x \times y \times z 的积分。(y 表示被击中的靶上的数，x 表示其左侧最近且未被击中的靶上的数，z 表示其右侧最近且未被击中的靶上的数。如果其左侧不存在未被击中的靶，则 x 为 1；如果其右侧不存在未被击中的靶，则 z 为 1。)

计算完积分后，这块靶就会退出靶场（不在这排靶中）。

请计算击中所有靶后能得到的最高积分是多少？

例如：n=4，表示有4块靶，这4块靶上的数从左到右分别是 3, 2, 4, 6; 按照下列顺序打靶，可以得到最高积分：

1. 打 2 号靶，得到的积分是 24（3 \times 2 \times 4）；
2. 打 3 号靶，得到的积分是 72（3 \times 4 \times 6）；
3. 打 1 号靶，得到的积分是 18（1 \times 3 \times 6）；
4. 打 4 号靶，得到的积分是 6（1 \times 6 \times 1）； 最终获得的积分是 120（24 + 72 + 18 + 6）。

第一行输入一个整数 n（1 \leq n \leq 300），表示靶场上靶的数量。

第二行输入 n 个整数（1 \leq \text{整数} \leq 100），分别表示从左到右每块靶上的数，整数之间以一个空格隔开。

输出一个整数，表示击中所有靶后能得到的最高积分。

蓝桥杯