You are given $n$ integers $w_i (i = 0, 1, ..., n-1)$ to be sorted in ascending order. You can swap two integers $w_i$ and $w_j$. Each swap operation has a cost, which is the sum of the two integers $w_i + w_j$. You can perform the operations any number of times.

Write a program which reports the minimal total cost to sort the given integers.

Constraints

* $1 \leq n \leq 1,000$
* $0 \leq w_i\leq 10^4$
* $w_i$ are all different

Input

In the first line, an integer $n$ is given. In the second line, $n$ integers $w_i (i = 0, 1, 2, ... n-1)$ separated by space characters are given.

Output

Print the minimal cost in a line.

Examples

Input

5
1 5 3 4 2


Output

7


Input

4
4 3 2 1


Output

10
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        System.out.println(minimumCost(a));
    }

    private static long minimumCost(int[] a) {
        int[] sorted = Arrays.copyOf(a, a.length);
        Arrays.sort(sorted);
        int[] indexes = new int[sorted[a.length-1]+1];
        for (int i = 0; i < a.length; i++) {
            indexes[sorted[i]] = i;
        }

        long cost = 0;
        for (int i = 0; i < a.length; i++) {
            int goalIndex = indexes[a[i]];
            if (goalIndex != i && goalIndex >= 0) {
                int cycleSize = 1;
                int cycleMin = a[i];
                int cycleSum = a[i];
                while (goalIndex != i) {
                    int nextInCycle = a[goalIndex];
                    cycleSize++;
                    if (nextInCycle < cycleMin) cycleMin = nextInCycle;
                    cycleSum += nextInCycle;
                    goalIndex = indexes[nextInCycle];
                    indexes[nextInCycle] = -1;
                }
                cost += Math.min(cycleSum + cycleMin * (cycleSize - 2),
                        cycleSum + cycleMin + sorted[0] * (cycleSize + 1));
            }
        }
        return cost;
    }
}

