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
"""Minimum cost Sort."""

def make_cycle(A):
    """Return a list which has the minimum element of A and
    switch elements cycles as list.

    A is a list whose elements' type is 'int'.
    """
    B = list(A)
    B.sort()
    cycle_list = [B[0]]
    for i, b in enumerate(B):
        if b:
            new_cycle = []
            new_cycle.append(b)
            B[i] = None
            si = A.index(b)
            while si != i:
                st = B[si]
                new_cycle.append(st)
                B[si] = None
                si = A.index(st)
            cycle_list.append(new_cycle)
    return cycle_list

def min_sorting_cost(A):
    """Return the minimum cost of sorting A.

    A is a list whose elements' type is 'int'.
    """
    cycles = make_cycle(A)
    min_w = cycles[0]
    cost = 0
    for c in cycles[1:]:
        n = len(c)
        min_cw = c[0]
        dec = (n - 1) * (min_cw - min_w)
        inc = 2 * (min_w + min_cw)
        if dec < inc:
            cost += sum(c) + min_cw * (n - 2)
        else:
            cost += sum(c) + min_cw * (n - 2) - dec + inc
    return cost


n = int(input())

A = list(map(int, input().split()))

ans = min_sorting_cost(A)

print(ans)