#1215. Never gonna give you up

Never gonna give you up

题目背景

你被骗了

Never gonna give you up

Never gonna let you down

image

题目介绍

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

  • 性质1:将一个串设为ss,满足s[begin]=s[end]=s[begin+1]=s[end1.]..=s[mid1]=s[mid+1]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]sum(l,r)表示a[l]+a[l+1]+...+a[r]

输入输出格式

输入

第一行一个正整数nn,表示序列元素个数 接下来nn行,每行一个正整数,表示aiai的值

输出

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

输入输出样例

5
1 2 3 2 1
9

数据范围与规定

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