Problem B
Building Highways

The country of Singanesia consists of $N$ cities, numbered from $1$ to $N$. From a recent survey, each city is assigned a level which denote how problematic it is. The $i$-th city have a problematic level of $A_ i$. To improve the welfare, recently there is a plan to build intercities highways. As problematic cities tend to hinder the development of the highway, the government decided to use the problematic level to estimate how difficult it is to build a highway between two cities. The difficulty level of building a highway connecting $i$-th city and $j$-th city is $A_ i+A_ j$. Now, the government plan for the intercities highways goes like the following:

• They will build several highways such that from any city, someone can go to any other cities using the built highways

• They will minimize the sum of the difficulty level of building the intercities highways

As the leader for this development plan, your task is to find the minimum sum of the difficulty level to build the intercities highways.

Input

The first line contains an integer $N$ ($1 \leq N \leq 200\, 000$).

The next line contains $N$ integers $A_ i$ ($1 \leq A_ i \leq 1\, 000\, 000$).

Output

Output the minimum sum of the difficulty level to build the highways.

Subtasks

1. ($30$ Points): $N \leq 1\, 000$.

2. ($30$ Points): All $A_ i$ have the same value.

3. ($40$ Points): No additional constraints.

Explanation

Below is the explanation for the first sample. Each line denotes the difficulty of building the highway. The red lines denote one possible intercities highways plan with the minimum sum of the difficulty level.

Below is the explanation for the second sample.

4
2 3 2 5

16

5
3 1 7 5 1

20