408960: GYM103389 D 修建道路

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

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

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

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

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

4
2 8 5 4

21