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 mklist(B,D,V):
    min = 10000
    for key,val in enumerate(B):
        D[val] = key
        V[val] = 0
        if min > val:
            min = val
    return min

def solve(A,V,D,min):
    cost = 0
    for key, val in enumerate(A):
        if V[val] != 0:
            continue
        W = []
        wmin = 10000
        tw = 0
        k1 = key
        v = val
        while(1):
            k2 = D[v]
            if V[v] == 1:
                break
            W.append(v)
            V[v] = 1
            if wmin > v:
                wmin = v
            tw += v
            #print("key={} k1={} k2={} v={} Vv={}".format(key,k1,k2,v,V[v]))
            k1 = k2
            v = A[k1]
        n = len(W)
        t1 = tw + ((n - 2) * wmin)
        t2 = tw + wmin + ((n + 1) * min)
        if t1 < t2:
            cost += t1
        else:
            cost += t2
    return cost

def main():
    num = int(input())
    A = list(map(int,input().split()))
    B = sorted(A)
    D = {}
    V = {}
    min = mklist(B,D,V)
    cost = solve(A,V,D,min)
    print(cost)

if __name__ == '__main__':
    main()