Minimum Cost Sorting

You are given a sequence of N distinct integers. In one operation, you are allowed to swap any two numbers in the sequence, and the cost of that swap is the sum of the two numbers being swapped.

Your goal is to sort the sequence in ascending order minimizing the total cost. Compute the minimum cost needed.

Hint: The solution involves decomposing the permutation into cycles. For a cycle with k elements, let s be the sum of the elements, and m_c be the minimum element in the cycle. Also, let m be the global minimum of the array. Then the cost can be computed by one of the following methods:

• Direct method: \( cost_1 = s + (k-2) \times m_c \)
• Using the global minimum: \( cost_2 = s + m_c + (k+1) \times m \)

The answer is the sum of minimum costs over all cycles. Use the strategy that minimizes the cost for each cycle.

inputFormat

The first line contains an integer N, the number of elements in the sequence.

The second line contains N distinct integers separated by spaces.

outputFormat

Output a single integer which is the minimum cost to sort the sequence in ascending order.

sample

3
3 2 1

4