#940 Pepero Exchange

Statement

Statement language

There are $2N$ people in a row, numbered $1$ through $2N$ in order. Between people $i$ and $i+1$ is a fence of height $H_i$ for $1\leq i<2N$ . The cost of pairing people $a<b$ is $\max(H_a,H_{a+1},\ldots,H_{b-1})$ . Partition all people into $N$ pairs, with each person in exactly one pair, and minimize the sum of the costs. Intervals representing pairs may overlap or cross.

Input

The input is given in the following format:

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

Output

Print the minimum possible sum of costs.

Constraints

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

Subtasks

#	Score	Constraints
1	20	$N \leq 8$ .
2	80	No additional constraints.

Samples

Sample 1

Input

2
100 1 100

Output

101

Sample 2

Input

1
7

Output

7

Sample 3

Input

3
4 4 4 4 4

Output

12