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
#include <algorithm>
#include <iostream>

int minimumCountSort(int n, int* a)
{
    int sum_a = 0;
    int min = 100000;
    int B[1000], T[10001];
    bool V[1000];
    int ans = 0;
    int min_a = 10000;

    //?????????
    for (int i = 0; i < n; i++) {
	B[i] = a[i];
	V[i] = false;
	if (min_a > a[i]) {
	    min_a = a[i];
	}
    }
    std::sort(B, B + n);
    for (int i = 0; i < n; i++) {
	T[B[i]] = i;
    }
    int minSolve = sum_a + (n - 2) * min;
    int* b = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
	if (V[i]) {
	    continue;
	}
	int cur = i;
	int sum = 0;
	int min = 10000;
	int an = 0;
	while (1) {
	    V[cur] = true;
	    an++;
	    int v = a[cur];
	    min = std::min(min, v);
	    sum += a[cur];
	    cur = T[v];
	    if (V[cur]) {
		break;
	    }
	}
	ans += std::min(sum + (an - 2) * min, min + sum + (an + 1) * min_a);
    }
    return ans;
}

int main()
{
    int n = 0;
    std::cin >> n;
    int* a = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
	std::cin >> a[i];
    }
    int answer = minimumCountSort(n, a);
    std::cout << answer << std::endl;
}