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<bits/stdc++.h>
using namespace std;
int vmax=10000;
int A[1005],B[1005],T[20000];
bool M[1005];
int main()
{
	int S;//记录每个环内元素值的总和
	int Min;//记录整个数组的最小值 
	int num=0;//记录最小成本 
	int m;//记录整个环内最小值，方便调换元素 
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
		B[i]=A[i];
		M[i]=false;//false表示该位置的元素没有合理归为 
	}
	sort(B,B+n);
	Min=B[0]; 
	for(int i=0;i<n;i++) T[B[i]]=i;//B[i]这个数排序后的位置 
	for(int i=0;i<n;i++)
	{
		int weizhi=i;
		int S=0;//记录环内元素总值 
		int m=vmax;
		int ans=0;//记录环内元素个数
		if(M[weizhi]) continue;//该位置元素归为则跳过 
		 
		while(1)
		{
			M[weizhi]=true;//没有归为
			ans++;
			int cur=A[weizhi];
			S+=cur;
			m=min(m,cur);
			weizhi=T[cur];
			if(M[weizhi]) break;
		 }
		  num+=min((S+(ans-2)*m),S+m+(ans+1)*Min);
	}
	printf("%d\n",num);
	
	
} 
