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 main(){
    int n;
    cin >> n;
    int A[n], B[n];
    for(int i = 0; i < n; i++){
        cin >> A[i];
        B[i] = A[i];
    }
    sort(A, A+n);
    int j = 0, s = 0, cnt, t, s1, s2;
    while(j < n){
        if(A[j] != B[j]){
            s1 = s2 = cnt = 0;
            int l = j;
            while(B[l] != A[j]){
               l++;
            }
            int k = j;
            while(B[k] != A[l]){
                k++;
            }
            t = B[l]; B[l] = B[k]; B[k] = t; cnt++;
            s1 += B[k] + B[l];
            while(A[k] != B[k]){
                l = j;
                while(B[l] != A[k]){
                    l++;
                }
                t = B[l]; B[l] = B[k]; B[k] = t; cnt++;
                s1 += B[l] + B[k];
                k = l;
            }
            s2 = (A[0] + A[j])*2 + s1 - cnt*(A[j] - A[0]);
            if(s1 >= s2) s = s + s2;
            else s = s + s1;
        }
        j++;
    }

    cout << s << endl;

    return 0;
}
