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

using namespace std;

int main() {
    size_t n;
    scanf("%zu", &n);

    vector<int> w(n);
    map<int, size_t> m;
    int minw=1e8;
    for (size_t i=0; i<n; ++i) {
        scanf("%d", &w[i]);
        m[w[i]] = 0;
        if (minw > w[i])
            minw = w[i];
    }

    {
        size_t k=0;
        for (pair<const int, size_t> &p: m)
            p.second = k++;
    }

    int res=0;
    vector<bool> done(n);
    for (size_t i=0; i<n; ++i) {
        if (done[i]) continue;

        int count_=0, minc=1e8, sum=0;
        size_t cur=i;
        for (count_=0; ; ++count_) {
            if (done[cur]) break;

            done[cur] = true;
            if (minc > w[cur])
                minc = w[cur];

            sum += w[cur];
            cur = m[w[cur]];
        }

        res += sum + min((count_-2)*minc, minc+minw*(count_+1));
    }

    printf("%d\n", res);
    return 0;
}