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<cstdio>
#include<algorithm>

using namespace std;

const int maxn=1e3+5;
const int N=1e4+5;

int s[maxn],b[maxn],n,minn=N,book[maxn],weizhi[N];

int solve()
{
    int ans=0;
    for(int i=0;i<n;i++){
        b[i]=s[i];
    }
    sort(b,b+n);
    for(int i=0;i<n;i++){
        weizhi[b[i]]=i;
    }
//    for(int i=1;i<=10;i++){
//        cout<<weizhi[i]<<" ";
//    }
//    cout<<endl;
    for(int i=0;i<n;i++){
        if(book[i]){
            continue;
        }
        int cnt=0,cixiao=N,cur=i,temp=0;
        while(1){
            book[cur]=1;
            int v=s[cur];
            temp+=v;
            cnt++;
            cixiao=min(cixiao,s[cur]);
            cur=weizhi[s[cur]];
            if(book[cur]){
                break;
            }
        }
        ans+=min(temp+(cnt-2)*cixiao,cixiao+temp+(cnt+1)*minn);
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&s[i]);
        minn=min(s[i],minn);
    }
  //  cout<<minn<<endl;
    int ans=solve();
    cout<<ans<<endl;
    return 0;
}
/*
5
1 5 3 4 2
6
2 1 8 10 7 9
7
4 3 2 7 1 6 5
*/

