时间限制：1000ms　内存限制：512MB

题目描述

程老师的炼金炉是一台上了年纪的老设备，炉壁上刻着一圈从 0 到 99 的刻度。这台炉子的温度传感器只能识别两位数以内的浓度值，所以任何原料进入炉膛后，浓度都会被折算到 0 至 99 的范围内。这个特性是几十年前设计时就定下来的，炉子内部的齿轮、阀门、仪表全部按照这个量程制造，没法改动。

炉子旁边摆着 $n$ 桶原料，从左到右排成一行，第 $i$ 桶的浓度为 $a_i$。每桶的浓度是一个 0 到 99 之间的整数。程老师需要用这台炉子把所有原料炼成一桶成品。

每次操作的流程是这样的：程老师从当前摆放的原料中选出相邻的两桶，把它们一起倒进炉膛。炉子会把这两桶混合，混合后的成品浓度等于这两桶浓度之和对 100 取余——也就是刻度盘上显示的数值。混合完成后，这桶成品会被放回原来两桶中靠左的那个位置，右侧的空位消失，剩余的原料仍然从左到右紧密排列。

每次混合都会消耗炉子的燃料。消耗的燃料量等于这次操作前两桶原料的浓度之和——是取余之前的真实浓度之和，不是取余之后的成品浓度。程老师需要反复进行这样的操作，每次选出相邻的两桶合并，直到只剩一桶为止。

合并的顺序会影响总燃料消耗。同样 $n$ 桶原料，先合并哪一对、后合并哪一对，得到的总代价可能相差很大。程老师想省点燃料，所以他想知道：把 $n$ 桶原料合并成一桶，最少需要消耗多少燃料？

输入格式

第一行一个整数 $n$，表示原料的桶数。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每桶原料的浓度。

输出格式

一行一个整数，表示合并成一桶所需的最小总代价。

数据范围

• 对于所有测试点，$1 \le n \le 300$，$0 \le a_i \le 99$。
• 子任务分档如下：

特殊性质 A：所有桶的浓度相同。

特殊性质 B：所有桶的浓度之和不超过 99。

样例

样例 1

输入：

3
30 40 50

输出：

190

样例 2

输入：

3
60 70 80

输出：

240

样例 3

输入：

4
40 50 60 70

输出：

280

样例 4

输入：

1
42

输出：

0

样例解释

样例 1：一种最优方案是先合并第 1 桶和第 2 桶（浓度 30 和 40），代价为 $30 + 40 = 70$，新桶浓度为 $70 \bmod 100 = 70$。此时序列变为 70、50。再合并这两桶，代价为 $70 + 50 = 120$，新桶浓度为 $120 \bmod 100 = 20$。总代价为 $70 + 120 = 190$。如果先合并第 2 桶和第 3 桶，代价为 $40 + 50 = 90$，新桶浓度为 90；再合并 30 和 90，代价为 120；总代价 $90 + 120 = 210$，比 190 更大。

样例 2：先合并第 1 桶和第 2 桶（浓度 60 和 70），代价为 $60 + 70 = 130$，新桶浓度为 $130 \bmod 100 = 30$。再合并 30 和 80，代价为 $30 + 80 = 110$。总代价 $130 + 110 = 240$。

样例 3：最优方案是先合并第 2 桶和第 3 桶（浓度 50 和 60），代价为 $50 + 60 = 110$，新桶浓度为 $110 \bmod 100 = 10$。序列变为 40、10、70。再合并前两桶（浓度 40 和 10），代价为 $40 + 10 = 50$，新桶浓度为 $50 \bmod 100 = 50$。序列变为 50、70。最后合并，代价为 $50 + 70 = 120$，新桶浓度为 $120 \bmod 100 = 20$。总代价为 $110 + 50 + 120 = 280$。

样例 4：只有 1 桶原料，不需要任何合并操作，代价为 0。