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
#! /usr/local/bin/python3
# coding: utf-8

from itertools import product
from math import inf
from sys import setrecursionlimit

setrecursionlimit(10000)

ws = []
min_weight = inf


def swap(w, i, j):
    tmp = w[i]
    w[i] = w[j]
    w[j] = tmp


def try_next(w, total, hand):
    global min_weight

    if total > min_weight:
        return

    if w == ws:
        min_weight = min(total, min_weight)
        return

    for i, j in product(range(len(w)), range(len(w))):
        if i >= j:
            continue
        wnew = w[:]
        swap(wnew, i, j)
        hnew = hand[:]
        hnew.append((i, j))
        try_next(wnew, total + w[i] + w[j], hnew)

    return


def first_try(w):
    global ws

    weight = 0
    for i in reversed(range(len(w))):
        j = w.index(ws[i])
        if i != j:
            weight += w[i] + w[j]
            swap(w, i, j)
    return weight


def main():
    global ws, min_weight

    n = int(input())
    w = [int(x) for x in input().split()]
    ws = sorted(w)

    min_weight = first_try(w[:])
    try_next(w, 0, [])
    print(min_weight)


main()

