408960: GYM103389 D 修建道路

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. 修建道路time limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

比特镇有 $$$n$$$ 个村庄,编号依次为 $$$1$$$ 到 $$$n$$$。现在需要修建 $$$n-1$$$ 条双向道路将这些村庄连通起来,每条道路的端点只能是这 $$$n$$$ 个村庄之一。准确地说,如果要修建一条直接连接村庄 $$$i$$$ 与村庄 $$$j$$$ 的双向道路 ($$$1\leq i\leq j\leq n$$$),那么需要支付 $$$\max_{i\leq k\leq j}\{a_k\}$$$ 的费用。

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

Input

第一行包含一个正整数 $$$n$$$ ($$$1\leq n\leq 200\,000$$$),表示村庄的数量。

第二行包含 $$$n$$$ 个正整数 $$$a_1,a_2,\dots,a_n$$$ ($$$1\leq a_i\leq 10^9$$$)。

Output

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

ExampleInput
4
2 8 5 4
Output
21

加入题单

上一题 下一题 算法标签: