Background

Special for beginners, ^_^

Description

比特镇有 n 个村庄，编号依次为 1 到 n。现在需要修建 n−1 条双向道路将这些村庄连通起来，每条道路的端点只能是这 n 个村庄之一。准确地说，如果要修建一条直接连接村庄 i 与村庄 j 的双向道路 (1≤i≤j≤n)，那么需要支付 在索引范围从 i 到 j 之间取值的元素 ak 中最大的元素的费用。

请写一个程序，找到一个总费用最小的修路方案，使得任意两个村庄都能通过这些道路直接或间接到达。

Format

Input

第一行包含一个正整数 n (1≤n≤200000)，表示村庄的数量。

第二行包含 n 个正整数 a1​,a2​,…,an​ (1≤ai​≤1e9)。.

Output

输出一行一个整数，即所需的最小总费用。

Samples

4
2 8 5 4

21

Limitation

1s, 1024KiB for each test case.