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 minimum_cost(A, m, k):
    """整数列 A を最小コストソートでソートした場合の総コストを返す。

    A 内の整数は 0 <= <= k のすべて異なる整数であり、
    m がその中で最小の数。
    """
    # A 内の整数 i の出現数を C[i] に記録していく。
    C = [0 for _ in range(0, k + 1)]
    for x in A:
        C[x] += 1
    
    # A 内の i 番目の整数のソート後の位置（0 起点）を C[i] に記録する。
    C[0] -= 1
    for i in range(1, k + 1):
        C[i] += C[i - 1]

    total_cost = 0
    n = len(A)
    for i in range(n):
        j = i
        length = 0
        sum_weight = 0
        cur_min = k + 1
        while C[A[j]] >= 0:
            length += 1
            sum_weight += A[j]
            if A[j] < cur_min:
                cur_min = A[j]
            z = C[A[j]]
            C[A[j]] = -1
            j = z
        if length >= 3:
            if cur_min > m:
                total_cost += min(sum_weight + cur_min * (length - 2),
                                  (sum_weight - cur_min) + m * (length - 1) + 2 * (m + cur_min))
            else:
                total_cost += sum_weight + cur_min * (length - 2)
        elif length == 2:
            total_cost += sum_weight

    return total_cost

if __name__ == '__main__':
    import sys

    n = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    print(minimum_cost(A, min(A), max(A)))
