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
MAXV = 10**4

if __name__ == '__main__':
    n = int(raw_input())
    # input, range[1, n], according to counting sort
    A = [0] + map(int, raw_input().split())
    # counter, range: [0, k]
    # so why use counting sort?
    # because it's easy to find where an element go after sorting
    C = [0 for i in range(MAXV + 1)]
    min_of_all = MAXV + 1

    for i in range(1, n + 1):
        C[A[i]] += 1
        min_of_all = min(min_of_all, A[i])

    for i in range(1, MAXV + 1):
        C[i] += C[i - 1]

    # find all cycles of moves
    # if V[i] is 1, then A[i] is already covered in some cycle
    V = [0 for i in range(n + 1)]
    total_cost = 0
    for i in range(1, n + 1):
        if V[i] == 1:
            continue
        V[i] = 1  # mark as visited
        size_of_cycle = 1  # the number of elements in the cycle
        min_of_cycle = A[i]
        sum_of_cycle = A[i]
        j = i  # iterator
        while True:
            j = C[A[j]]
            if i == j:
                break
            V[j] = 1
            size_of_cycle += 1
            sum_of_cycle += A[j]
            min_of_cycle = min(min_of_cycle, A[j])
        if size_of_cycle == 1:
            # only one element, no move, cost is zero
            continue

        cost = sum_of_cycle + (size_of_cycle - 2) * min_of_cycle
        if min_of_all < min_of_cycle:
            # swap back and forth, positive
            diff = 2 * (min_of_all + min_of_cycle)
            # diff in the sum of the cycle, negative
            diff += min_of_all - min_of_cycle
            # diff in (n-2)*min(w), negative
            diff += (size_of_cycle - 2) * (min_of_all - min_of_cycle)
            if diff < 0:
                cost += diff
        total_cost += cost

    print total_cost
