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 get_weights():
    raw_input()
    return map(int, raw_input().split())

#weights: list
def minimam_cost_sort(weights):
    mw = min(weights)
    s_w = sorted(weights)
    lol = []
    for i in range(len(weights)):
        if weights[i] != 0:
            j = weights[i]
            idx = s_w.index(j)
            weights[i] = 0
            l = [j]
            while weights[idx] != 0:
                l.append(weights[idx])
                j = weights[idx]
                weights[idx] = 0
                idx = s_w.index(j)
            l.sort()
            lol.append(l)

    lol.sort()
    s = 0
    for l in lol:
        s += get_wol(l, mw)

    print s

def get_wol(l, mw):
    sub = (l[0] - mw) * (len(l) - 1) - (l[0] + mw) * 2
    s = sum(l) + (l[0] * (len(l) - 2))
    if sub > 0:
        return s - sub
    return s

minimam_cost_sort(get_weights())