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):
    correct_a = sorted(A)
    correct_index = {n: i for i, n in enumerate(correct_a)}
    ans, min_n = 0, correct_a[0]
    cycles = []
    used = [0]*len(A)
    for i in filter(lambda i: not used[i], range(len(A))):
        used[i] = 1
        cycle, next_i = [i], correct_index[A[i]]
        while next_i != i:
            cycle.append(next_i)
            used[next_i] = 1
            next_i = correct_index[A[next_i]]
        cycles.append(cycle)

    for cycle in cycles:
        if len(cycle) == 2:
            ans += correct_a[cycle[0]] + correct_a[cycle[1]]
        elif len(cycle) > 2:
            ans += (min(correct_a[cycle[0]]*(len(cycle)-1), correct_a[cycle[0]]*2 + min_n*(len(cycle)+1))
                    + sum(correct_a[i] for i in cycle[1:]))

    return ans


if __name__ == "__main__":
    input()
    a = list(map(int, input().split()))
    print(solve(a))
