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
N = int(input())
A = list(map(int, input().split()))  # ソート前の並び
B = sorted(A)  # ソート後の並び
c = 0  # 移動コスト

# 1 3 4 ... N 2 -> 1 2 3 4 ... N
# パターンa) 移動すべき要素（グループ）の中での最小(2:B[i]） を使って移動させる
# 1 3 4 2 : スタート
# 1 3 2 4 : <1>
# 1 2 3 4 : <2>
#
# パターンb) 一旦 最小(1:B[0]) と グループ最小(2:B[i]) を交換して始める
# 1 3 4 2 : スタート
# 2 3 4 1 : B[i] + B[0] 追加
# 2 3 1 4 : <1> - (B[i] - B[0])
# 2 1 3 4 : <2> - (B[i] - B[0])
# 1 2 3 4 : B[i] + B[0] 追加

for i in range(N - 1):  # 最後の一つは、手前が揃っていれば揃っている
    t = cnt = 0
    ai = A.index(B[i])  # 並べ替え前の B[i] がいる場所

    while ai != i:  # 並べ替え前と同じでない場合
        y = A.index(B[ai])  # 更に次の
        A[ai], A[y] = B[ai], B[i]  # スワップ
        cnt += 1
        t += B[ai] + B[i]  # このときのコスト
        ai = y
    if cnt:
        # パターンa と パターンb を比較して、コストが小さい方に決める
        c += min(t, (B[i] + B[0]) * 2 + t - (B[i] - B[0]) * cnt)
print(c)

