빼빼로 교환

$2N$명의 사람이 $1$번부터 $2N$번까지 순서대로 한 줄로 서 있다. 각 $i$ ($1\leq i<2N$)에 대해 $i$번 사람과 $(i+1)$번 사람 사이에는 높이 $H_i$인 담장이 있다. 두 사람 $a,b$ ($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$ ().