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 main(){
    int n;
    cin>>n;
    vector<int> w(n),c(n),j(10001),index(10001);
    for(int i=0;i<n;i++){
        cin>>w[i];
    }

    c=w;
    for(int i=0;i<10001;i++){
        j[i]=1;
    }
    int m=10001,ans=0;
    for(int i=0;i<n;i++){
        m=min(m,w[i]);
    }
    sort(c.begin(),c.end());
    for(int i=0;i<n;i++){
        index[c[i]]=i;
    }
    for(int i=0;i<n;i++){
        if(j[w[i]]){
            int cnt=0,x=w[i],min1=10001;
            do{
                j[x]=0;
                min1=(min1,x);
                ans+=x;
                x=w[index[x]];
                cnt++;
            }while(x!=w[i]);
            if(cnt==1) ans-=x;
            else if(cnt>=3){
                ans+=min(min1*(cnt-2),min1+m*(cnt+1));
            }            
        }
    }
    cout<<ans<<endl;
}
