题目背景

你被骗了

Never gonna give you up

Never gonna let you down

题目介绍

给你一个序列，每个值为$ai$,每次你可以从其中移除一个满足性质1的串， 代价是$sum(区间起点，区间终点)$,求全部移除的最小代价

• 性质1:将一个串设为$s$，满足$s[begin] = s[end] = s[begin+ 1]= s[end - 1.]..= s[mid - 1]= s[mid + 1]$
• $sum(l,r)表示a[l]+a[l+1]+...+a[r]$

输入输出格式

输入

第一行一个正整数$n$，表示序列元素个数 接下来$n$行，每行一个正整数，表示$ai$的值

输出

一个正整数，表示全部移除的最小代价

输入输出样例

5
1 2 3 2 1

9

数据范围与规定

对于100%的数据，保证 $2 \leq n \leq 100,2 \leq ai \leq 10000$