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>
#define MAX 10000
using namespace std;
int main(){
    int n,mini=MAX,data[1000],x[1000],pos[MAX+1]; cin>>n;
    for(int i=0;i<n;++i){
	cin>>data[i];
	x[i]=data[i];
	if(mini>data[i]) mini=data[i];
    }
    for(int i=0;i<n-1;++i)
	for(int j=n-1;j>i;--j)
	    if(x[j-1]>x[j]) swap(x[j-1],x[j]);
    for(int i=0;i<n;++i) pos[x[i]]=i;
    int sumn=0,flag[1000]={};
    for(int i=0;i<n;++i){
	if(flag[i]) continue;
	int m=MAX,sum=0,cnt=0,cur=i;
	do{
	    int val=data[cur];
	    flag[cur]=1;
	    sum+=val;
	    cur=pos[val];
	    if(m>val) m=val;
	    ++cnt;
	}while(!flag[cur]);
	if(sum+(cnt-2)*m<m+sum+(cnt+1)*mini) sumn+=sum+(cnt-2)*m;
	else sumn+=m+sum+(cnt+1)*mini;
    }
    cout<<sumn<<endl;
    return 0;
}

