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 bisect


def sorted_index(A):
    # Aをソートした後のindexのリスト
    A_ = sorted(A)
    B = []
    for a in A:
        idx = bisect.bisect_left(A_, a)
        B.append(idx)
    return B


def cyclic_factorize(A):
    # Aを巡回置換分解する
    B = sorted_index(A)
    checked = [False] * len(A)
    cycle_lst = []
    for i, a in enumerate(A):
        if checked[i]:
            continue
        now = i
        checked[now] = True
        cycle = [a]
        next = B[now]
        while not checked[next]:
            now = next
            next = B[now]
            cycle.append(A[now])
            checked[now] = True
        cycle_lst.append(cycle)
    return cycle_lst


N = int(input())
*W, = map(int, input().split())
cycle_lst = cyclic_factorize(W)
ans = 0
global_min = min(W)
for cycle in cycle_lst:
    l = len(cycle)
    s = sum(cycle)
    local_min = min(cycle)
    ans += s + min((l - 2) * local_min, local_min + (l + 1) * global_min)
print(ans)
