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
//The Number of Inversions
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

struct Weight {
    int id = 0;
    int weight = 0;
    bool searched = false;
    bool operator < (const Weight &w) const {
        return weight < w.weight;
    }
};

int main() {
    int n, s = INT_MAX;
    cin >> n;
    Weight W[n];
    for(int i=0; i<n; i++) {
        cin >> W[i].weight;
        W[i].id = i;
        s = min(s, W[i].weight);
    }

    sort(W, W+n);

    int cost = 0;
    for(int i=0; i<n; i++) {
        if(W[i].searched) continue;
        int id = i, c = 0, size = 0;
        while(1) {
            W[id].searched = true;
            c += W[id].weight;
            id = W[id].id;
            size++;
            if(id == i) break;
        }
        if(size != 1)
            cost += c + min((size-2)*W[i].weight, W[i].weight+(size+1)*s);
    }
    cout << cost << endl;
}
