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
import java.util.Scanner;
import java.util.Arrays;

class Main {
	private static	int num;
	private static	int[]  array;
	
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		num = scanner.nextInt();//要素数
		array = new int[num];
		//配列作成
		for(int i = 0; i < num; i ++ ){
			array[i] = scanner.nextInt();
		}
		//計算結果を出力
		System.out.println( cost() );
		
		scanner.close();
	}
	//最小コスト
	public static int cost(){ 
		int sorted[] = array.clone();		//クローンを作って
        Arrays.sort(sorted);			//昇順にしておいて比べる
		int mincost = 0;
		int sub;
		int comp = 0;

		for(int i = 0; i < num; i ++ ){
			comp = indexOf(sorted[i]);		//比較結果
            int count = 0;
			//比較結果によって中へ
            while (comp > i) {
                count ++;								//whileの中に入った数
                sub = indexOf(sorted[comp]);	//比較結果
                mincost += array[sub];
                int work = array[comp];
                array[comp] = array[sub];
                array[sub] = work;
                comp = sub;								//比較対象をずらしていく
            }
			//値の小さいほうをコストに
            mincost += Math.min(sorted[i] * count,
            		sorted[i] * 2 + sorted[0] * (count + 2));
        }
		return mincost;
	}
	
	public static int indexOf(int comp) {
        //一致した場所を返し、一致しなかったら-1
		for (int i = 0; i < num; i++) {
            if (array[i] == comp) {
                return i;
            }
        }
        return -1;
    }
}
