Given a complete graph with $n$ vertices, labeled $1$ to $n$, the weight of the edge between two vertices $i$ and $j$ ($i \neq j$) is $a_{i+j}$. Find the weight of the minimum spanning tree of this graph. You only need to output the sum of the edge weights of the minimum spanning tree.

Input

The first line contains a positive integer $n$ ($2 \leq n \leq 2 \times 10^5$), representing the number of vertices in the graph.

The second line contains $2n-3$ positive integers, representing $a_{3} \sim a_{2n-1}$ ($1 \leq a_i \leq 10^9$).

Output

A single line containing a positive integer representing the answer.

Examples

Input 1

4
7 6 7 6 4

Output 1

16

Input 2

8
21 5 28 58 73 32 43 96 72 54 35 28 5

Output 2

151

Subtasks

For $20\%$ of the test cases: $n \leq 1000$.

For $30\%$ of the test cases: $n \leq 10000$.

For another $20\%$ of the test cases: $a_i$ are generated uniformly at random in $[1, 10^9]$.

For all test cases: $1 \leq n \leq 2 \times 10^5$, $1 \leq a_i \leq 10^9$.