给定一个包含 $n$ 个数字的序列 $a_1, a_2, \dots, a_n$。你的任务是按照从大到小的顺序移除所有元素，并使总操作代价最小。相等的元素可以按任意顺序移除。你可以执行以下三种操作：

• 将第一个元素移动到序列末尾。
• 将最后一个元素移动到序列开头。
• 移除第一个元素，前提是序列中不存在比它更大的元素。

移动操作的代价等于被移动元素的值。移除操作没有代价。求出将序列变为空序列所需的最小总代价。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$)。

输出格式

输出一个整数，表示最小总代价。

样例

样例输入 1

6
6 10 6 5 4 5

样例输出 1

16

说明

最优的操作序列如下：

• $(6, 10, 6, 5, 4, 5)$，将第一个元素移动到末尾。代价为 $6$。
• $(10, 6, 5, 4, 5, 6)$，移除第一个元素。
• $(6, 5, 4, 5, 6)$，移除第一个元素。
• $(5, 4, 5, 6)$，将最后一个元素移动到开头。代价为 $6$。
• $(6, 5, 4, 5)$，移除第一个元素。
• $(5, 4, 5)$，移除第一个元素。
• $(4, 5)$，将第一个元素移动到末尾。代价为 $4$。
• $(5, 4)$，移除第一个元素。
• $(4)$，移除第一个元素。
• $()$，序列为空。

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