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 silly_sort(target):
    ranked = sorted(target)
    length = len(target)
    rings = [n for n in range(length)]
    all_cost = 0
    minimum = ranked[0]
    base_index = {}
    rank_index = {}
    for i, (t, r) in enumerate(zip(target, ranked)):
        base_index[t] = i
        rank_index[r] = i
    for i in range(length):
        if rings[i] != -1 and target[i] != ranked[i]:
            ring_sum = target[i]
            min_m = target[i]
            num_ring = 1
            next_index = rank_index[target[i]]
            next_num = target[next_index]
            while next_index != i:
                # print(i, next_index, target[i], min_m, ring_sum)
                num_ring += 1
                ring_sum += next_num
                min_m = min(min_m, next_num)
                rings[next_index] = -1
                next_index = rank_index[target[next_index]]
                next_num = target[next_index]
            # print(min((ring_sum + min_m * (num_ring - 2) ), (ring_sum + min_m + minimum * (num_ring + 1) ) ))
            all_cost += min((ring_sum + min_m * (num_ring - 2) ), (ring_sum + min_m + minimum * (num_ring + 1) ) )
        rings[i] = -1
    return all_cost

l = int(input())
t = [int(n) for n in input().split(" ")]
print(silly_sort(t))
