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 <algorithm>
#include <map>
#define MAX 1010
#define INF 1e+5
using namespace std;

int Minimum_Cost_Sort(int A[], int n)
{
	int B[MAX], visited[MAX], x = INF, ans = 0;
	map<int, int> M;
	
	for (int i = 0;i < n;i++)
	{
		B[i] = A[i];
		visited[i] = false;
		x = min(x, A[i]);
	}
	
	sort(B, B+n);
	
	for (int i = 0;i < n;i++)
	{
		M[B[i]] = i;
	}
	
	for (int i = 0;i < n;i++)
	{
		int tmp = i;
		int circle_size = 0;
		int weight = 0;
		int mini = INF;
		
		do
		{
			visited[tmp] = true;
			weight += A[tmp];
			mini = min(mini, A[tmp]);
			tmp = M[A[tmp]];
			circle_size++;
		}while(!visited[tmp]);
		
		ans += min(weight + (circle_size-2) * mini, weight + (circle_size+1) * x + mini);
	}
	return ans;
}

int main ()
{
	int n, A[MAX];
	cin >> n;
	for (int i = 0;i < n;i++)
	{
		cin >> A[i];
	}
	
	int mini_cost = Minimum_Cost_Sort(A, n);
	
	cout << mini_cost << endl;
	
	return 0;
}
