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
# Minimum Cost Sort
# 交換に重みwぶんコストがかかる

# N <= 1000
# a <= 10000

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

B = sorted(zip(A, origin), key=lambda x: x[0])


class UnionFind():
    def __init__(self, n):
        self.g = [[i] for i in range(n)]

    def root(self, x):
        if self.is_root(x):
            return x

        self.g[x] = self.root(self.g[x])
        return self.g[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False

        # yにxをくっつける
        if x < y:
            x, y = y, x
        self.g[y] += self.g[x]
        self.g[x] = y

        return True

    def size(self, x):
        return -self.root(x)

    def is_root(self, x):
        if type(self.g[x]) is list:
            return True
        return False


G = UnionFind(N)
for i, b in enumerate(B):
    G.unite(i, b[1])


min_g = min(A)
cost = 0
for i in range(N):
    if G.is_root(i):
        W = [A[j] for j in G.g[i]]
        n_w = len(W)
        sum_w = sum(W)
        min_w = min(W)

        cost1 = sum_w + min_w*(n_w-2)
        cost2 = cost1 + 2*(min_w + min_g) - (min_w-min_g)*(n_w-1)
        cost += min(cost1, cost2)

print(cost)

