切割序列

"我能打。"CC说，"概率往上加。"

你看着屏幕上的数字——41%，56%，63%，97%。这些数字像牢笼，把你们锁在Zero的逻辑里。

"你说得对。"你说，"我不能只用Zero的算法。我要用自己的。"

"咋个切？"CC问。

"切序列。"你说，"Zero的核心代码是一个长序列——连续的数字，没有断点。我要把它切成段，每段独立处理。"

"一段一段吃？"

"对。"你说，"如果整个序列一起处理，状态太多，算不过来。切成段，每段内部做DP，段与段之间再合并。"

"那咋切？"

"找断点。"你说，"序列中某些位置是天然的断点——前面和后面没有依赖关系。在这些位置切，段与段独立。"

"比如？"

"比如。"你说，"第47个位置。Echo-0的代码在这里有一个循环回跳——从47跳回1。这就是断点。"

"循环？"

"对。"你说，"Zero的代码里有很多循环。每次循环结束，就是一个断点。"

你开始写。给定一个序列，找所有循环结束的位置，然后分段做DP。

"第一段。"你说，"位置1到47。"

"第二段。"你说，"位置48到94。"

"第三段。"你说，"位置95到141。"

"每一段都是47。"

"对。"你说，"47是循环周期。"

"那DP咋做？"

"每段内部做单调队列优化的DP。"你说，"段与段之间，只传递最后一个状态。"

"减少了多少状态？"

"从$O(n^2)$降到$O(n\times段数)$。"你说，"快了一个数量级。"

CC看着你，金属肩膀上有一道新刮痕。

"你算得比Zero快？"

"不是快。"你说，"是聪明。Zero不会切，它会硬算。我会切。"

"切是它的弱点。"

"对。"你说，"它以为代码是连续的，不可分。但我知道哪里能切。"

题目描述

给定一个长度为$n$的序列，要把它切成若干段。每段有一个代价。总代价是各段代价之和。求最小总代价。

输入格式

$n$。然后$n$个整数表示序列。

输出格式

最小总代价。

输入样例

5
1 2 3 4 5

输出样例

-1

提示

• 单调队列优化DP。
• $dp[i]$为前$i$个数的最小代价。
• $dp[i]=\min(dp[j]+cost(j+1,i))$。
• 如果$cost$满足四边形不等式或单调性，可以用单调队列优化。