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

std::vector<int> A, B;
std::unordered_map<int, int> map;
std::vector<bool> V;
int n;
int mmin;
int minCostSort(){
    int ans = 0;
    int min, cnt, tmp;
    for(int i = 0; i < n; i++){
	min = A[i];
	cnt = 0;
	if(V[i] == 1) continue;
	if(map[A[i]] == i){
	    V[i] = 1;
	    continue;
	}
	tmp = i;
	while(1){
	    if(V[tmp] == 1){
		break;
	    }
	    ans += A[tmp];
	    V[tmp] = 1;
	    cnt++;
	    min = std::min(min, A[tmp]);
	    tmp = map[A[tmp]];
	}
	ans += std::min((cnt - 2) * min, (cnt + 1) * mmin + min);
    }
    return ans;
}

int main(void){
    int ans;
    std::cin >> n;
    A.resize(n);
    V.resize(n);
    for(int i = 0; i < n; i++){
	std::cin >> A[i];
    }
    for(int i = 0; i < n; i++){
	V[i] = 0;
    }

    B = A;


    std::sort(B.begin(), B.end());

    mmin = B[0];
    for(int i = 0; i < n; i++){
	map[B[i]] = i;
    }

    ans = minCostSort();

    std::cout << ans << std::endl;

    return 0;

}

