#P18261. Express Rotations

Express Rotations

Express Rotations

给定一个长度为 nn 的序列 a1,a2,…,ana_1,a_2,\ldots,a_n。你需要从大到小删除所有元素,并使总代价最小。相等的元素可以按照任意顺序删除。

可以执行以下三种操作:

  • 将序列的第一个元素移到末尾,代价为被移动元素的值。
  • 将序列的最后一个元素移到开头,代价为被移动元素的值。
  • 删除序列的第一个元素,但要求当前序列中没有比它更大的元素。删除操作的代价为 00。

求将序列变为空序列的最小总代价。

输入格式

第一行包含一个整数 nn。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出一个整数,表示使序列变为空序列的最小总代价。

数据范围

  • 1≤n≤500 0001\le n\le500\,000;
  • 1≤ai≤1061\le a_i\le10^6;
  • 输入只有一组数据。

样例

6
6 10 6 5 4 5
16

样例解释

一种最优操作顺序如下:

  1. 将首项6移到末尾,代价6:(6,10,6,5,4,5)→(10,6,5,4,5,6)(6,10,6,5,4,5)\to(10,6,5,4,5,6)。
  2. 删除首项10,再删除首项6,得到 (5,4,5,6)(5,4,5,6)。
  3. 将末项6移到开头,代价6,得到 (6,5,4,5)(6,5,4,5)。
  4. 删除首项6,再删除首项5,得到 (4,5)(4,5)。
  5. 将首项4移到末尾,代价4,得到 (5,4)(5,4)。
  6. 依次删除5和4,得到空序列。

总代价为 6+6+4=166+6+4=16。