百力滋交换

$2N$ 个人按编号 $1$ 到 $2N$ 的顺序排成一行。对于 $1\leq i<2N$，第 $i$ 个人和第 $i+1$ 个人之间有高度为 $H_i$ 的围墙。将两个人 $a<b$ 配成一对的费用为 $\max(H_a,H_{a+1},\ldots,H_{b-1})$。将所有人分成 $N$ 对，使每个人恰好属于一对，求总费用的最小值。表示各对的区间可以重叠或交叉。

输入格式如下：

$N$ $H_1\ H_2\ \cdots\ H_{2N-1}$

输出总费用的最小值。

• $1 \leq N \leq 200\ 000$.
• $1 \leq H_i \leq 10^9$ ().