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
import copy
MAX_LENGTH = 1000
MAX_WEIGHT = 10001


def minimum_sort_cost(A):
    cost = 0
    n = len(A)
    s = min(A)
    B = sorted(A)
    V = [False] * n
    T = [None] * MAX_WEIGHT

    for i in range(n):
        T[B[i]] = i
    
    for i in range(n):
        if V[i]:
            continue

        cur = i
        circle_len = 0
        min_weight = MAX_WEIGHT
        circle_weight = 0

        while(True):
            V[cur] = True
            circle_len += 1
            weight = A[cur]
            min_weight = min(min_weight, weight)
            circle_weight += weight
            cur = T[weight]

            if V[cur]:
                break
        
        cost += min(circle_weight + (circle_len - 2) * min_weight,\
             min_weight + circle_weight + (circle_len + 1) * s)
    
    return cost


if __name__ == "__main__":
    n = int(input())
    *A, = map(int, input().split())
    print(minimum_sort_cost(A))
