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
def partition(a, p, r):
    x = a[r]
    i = p - 1
    for j in range(p, r):
        if a[j] <= x:
            i += 1
            tmp = a[i]
            a[i] = a[j]
            a[j] = tmp
    tmp = a[i+1]
    a[i+1] = a[r]
    a[r] = tmp
    return i + 1


def quick_sort(a, p, r):
    if p < r:
        q = partition(a, p, r)
        quick_sort(a, p, q-1)
        quick_sort(a, q+1, r)


def make_cyclic(w, v):
    flags = [True] * len(w)

    cyclics = []
    for i in range(len(w)):
        if flags[i]:
            flags[i] = False
            cycle = [w[i]]
            now = w[i]
            while True:
                j = v.index(now)
                if j == i:
                    break
                cycle.append(w[j])
                now = w[j]
                flags[j] = False
            cyclics.append(cycle)

    return cyclics


def min_cost_sort(w):
    v = w.copy()
    quick_sort(v, 0, len(v) - 1)

    cyclics = make_cyclic(w, v)

    ans = 0
    for cycle in cyclics:
        inner_cycle = min(cycle) * (len(cycle) - 2) + sum(cycle)
        outer_cycle = min(cycle) + min(set(w) - set(cycle)) * (len(cycle) + 1) + sum(cycle)
        ans += min(inner_cycle, outer_cycle)

    return ans

n = int(input())
w = [int(x) for x in input().split()]

print(min_cost_sort(w))
