Farmer John's Cow Sorting

Farmer John has n cows arranged in a line, where n satisfies \(1 \le n \le 10^5\). Each cow has a unique temperament level in the range \(1 \ldots 10^5\). Because cows with higher temperament are more likely to damage his milking equipment, FJ wants to reorder the cows so that their temperament levels are in ascending order.

In the process, Farmer John is allowed to swap the positions of any two cows (they need not be adjacent). However, swapping two cows with temperament values \(X\) and \(Y\) takes \(X+Y\) units of time. Help FJ compute the minimum total time needed to sort the cows in ascending order.

Hint: Think about how to break down the permutation into cycles. For each cycle with \(k\) elements, let \(S\) be the sum of the cycle's elements and \(m\) be the minimum element of the cycle. Let \(g\) be the global minimum across all cows. The cost for a cycle can be computed using one of the following methods:

[ \text{Cost}_1 = S + (k-2) \times m, \quad \text{or} \quad \text{Cost}_2 = S + m + (k+1) \times g. ]

Take the minimum of these two costs for each cycle to obtain the overall minimum cost.

inputFormat

The first line contains a single integer \(n\) representing the number of cows. The second line contains \(n\) space-separated integers, each representing the temperament level of a cow in the current order.

outputFormat

Output a single integer representing the minimum time required to sort the cows in ascending order.

sample

3
2 3 1

7