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())
w = list(map(int, input().split()))
b = w[:]
w.sort()
s = w[0]

class Solve():
    def __init__(self, w, b, s):
        self.w = w
        self.b = b
        self.s = s
        self.ans = 0
        self.v = [0] * n
    
    def sort(self):
        T = [0] * 10001
        for i in range(n):
            T[self.w[i]] = i
        for i in range(n):
            if self.v[i]:
                continue
            cur = i
            S = 0
            m = 10001
            an = 0
            while 1:
                self.v[cur] = 1
                an += 1
                l = self.b[cur]
                m = min(m, l)
                S += l
                cur = T[l]
                if self.v[cur]:
                    break
            self.ans += min(S + (an - 2) * m, S + m +(an + 1) * self.s)
        return self

cost = Solve(w, b, s).sort()
print(cost.ans)
