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>
using namespace std;

int getMinCost(int n, int a[]){
	
	bool flag[n];
	int b[n];
	int mn = 1 << 30;
	int mx = mn * -1;
	for(int i=0; i<n; i++){
		flag[i]=false;
		b[i] = a[i];
		mn = min(mn, a[i]);
		mx = max(mx, a[i]);
	}
	sort(b, b+n);
	
	int p[mx+1];
	for(int i=0;i<n;i++){
		p[b[i]] = i;
	}
	
	int cost=0;
	for(int i=0; i<n; i++){
		if(flag[i]) continue;
		int idx=i;
		int m=mx;
		int sum=0;
		int cnt=0;
		while(true){
			flag[idx]=true;
			int val=a[idx];
			sum+=val;
			cnt++;
			m=min(m,val);
			idx=p[val];
			if(flag[idx]) break;
		}
		int c1=sum+(cnt-2)*m;
		int c2=c1+(2*(m+mn));
		c2 -= (cnt-1)*(m-mn);
		cost+=min(c1, c2);
	}
	return cost;
}

int main(){
	
	int n;
	cin >> n;
	int a[n];
	for(int i=0; i<n; i++){
		cin >> a[i];
	}
	
	cout << getMinCost(n, a) << endl;
	return 0;
}

