Tom got \(N\) books, each having their own weight \(W_i\) (\(1 \le i \le N\)), from the library in order to study for the CS146 final exam (Just kidding, who actually studies?). Tom spent the last 8 hours preparing for the final and finally decided to call it a night and get a good night's rest. However, Tom, being a perfectionist, wants to reorder the books to be non-decreasing order of their weight!

Tom is able to swap any two of the \(N\) books, but to do so must carry the weight of both the books combined. More formally, if Tom swaps books \(i\) and \(j\), then he must carry a weight of \(W_i + W_j\) kilograms.

Tom is very tired from his study session, so he wants to carry the least amount of weight possible. Specifically, he wants to minimize the maximum weight he has to carry.

Tom is unsure how to solve this problem and cannot sleep without having his things in order. Help Tom find out the minimum amount of weight he must carry and do it quickly so that Tom can pass his Elementary Algorithm Design and Data Abstraction exam!

Constraints

\(1 \le N \le 10^5\)

\(1 \le W_i \le 10^9\)

It is guaranteed that the books are not already sorted in non-decreasing order.

Input Specification

The first line will contain one integer \(N\), the number of books.

The next line will contain \(N\) space-separated integers, \(W_i\), the weight of the \(i\)-th book.

Output Specification

Output the minimum maximum weight Tom has to carry to sort the books in non-decreasing order.

Sample Input 1

5
2 4 6 5 1

Sample Output 1

7

Explanation

Tom can swap the \(3\)rd and \(5\)th book making the order: \([2, 4, 1, 5, 6]\).

Then, Tom can swap the \(1\)st and \(2\)nd book making the order: \([4, 2, 1, 5, 6]\).

Finally, Tom can swap the \(1\)st and \(3\)rd book making the order: \([1, 2, 4, 5, 6]\).

In the first swap, Tom must carry \(1 + 6 = 7\) kilograms.

In the second swap, Tom must carry \(2 + 4 = 6\) kilograms.

In the third swap, Tom must carry \(1 + 2 = 3\) kilograms.

This means that the maximum weight Tom must carry is \(7\) kilograms.

It can be shown that this is optimal.

Sample Input 2

7
1 3 2 4 2 5 9

Sample Output 2

5