#P18261. Express Rotations
Express Rotations
Express Rotations
给定一个长度为 的序列 。你需要从大到小删除所有元素,并使总代价最小。相等的元素可以按照任意顺序删除。
可以执行以下三种操作:
- 将序列的第一个元素移到末尾,代价为被移动元素的值。
- 将序列的最后一个元素移到开头,代价为被移动元素的值。
- 删除序列的第一个元素,但要求当前序列中没有比它更大的元素。删除操作的代价为 。
求将序列变为空序列的最小总代价。
输入格式
第一行包含一个整数 。
第二行包含 个整数 。
输出格式
输出一个整数,表示使序列变为空序列的最小总代价。
数据范围
- ;
- ;
- 输入只有一组数据。
样例
6
6 10 6 5 4 5
16
样例解释
一种最优操作顺序如下:
- 将首项6移到末尾,代价6:。
- 删除首项10,再删除首项6,得到 。
- 将末项6移到开头,代价6,得到 。
- 删除首项6,再删除首项5,得到 。
- 将首项4移到末尾,代价4,得到 。
- 依次删除5和4,得到空序列。
总代价为 。