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 solve(A, N):
    answer = 0

    B = list(A)
    V = [False] * N
    T = [None] * 10001
    s = min(A)

    B.sort()

    # print(A)
    # print(B)

    for i in range(N):
        T[B[i]] = i

    for i in range(N):
        if V[i] is True:  # すでにカーソルが来ていたら飛ばす。
            continue

        cur = i  # カーソル
        S = 0
        m = 10000  # VMAX
        an = 0  # サイクルの長さ

        while True:
            V[cur] = True  # まずは今の位置を走査済みにする。
            an += 1  # サイクルの長さを増やす
            v = A[cur]  # 入力列の値
            m = min(m, v)  # このサイクルの最小値
            S += v  # 今の値の重さを足す。SはΣwi
            cur = T[v]  # 次のカーソルの位置を決める
            if V[cur]:  # 次のカーソルの位置がTrueなら
                break  # サイクルの始まりまで戻ってきたということ。

        # この状態で、
        # an = サイクルの長さ
        # S = wiの合計の重さ
        # m = このサイクルの最小値
        # の3つが分かっている。

        answer += min(S + (an - 2) * m, m + S + (an + 1) * s)

    return answer


N = int(input())
A = list(map(int, input().split()))

answer = solve(A, N)
print(answer)

