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;

public class Main {
    static int cost = 0;
    public static void main (String[] args) {
	Scanner scan = new Scanner(System.in);
	int n = Integer.parseInt(scan.nextLine());
	int[] w = new int[n];
	String[] inputA = scan.nextLine().split(" ");
	for (int i = 0; i < n; i++) {
	    w[i] = Integer.parseInt(inputA[i]);
	}
	sort(w, 0, n-1);
	System.out.println(cost);
    }
    static int partition (int[] a, int left, int right) {
	int middleIndex = findmiddle(a, left, right);
	int x = a[middleIndex];
	int i = left;
	int j = right;
	int tmp;
	while (true) {
	    while(a[i] < x) {
		i++;
	    }
	    while(a[j] > x) {
		j--;
	    }
	    if (i >= j) {
		break;
	    }
	    cost += a[i] + a[j];
	    tmp = a[i];
	    a[i] = a[j];
	    a[j] = tmp;
	    i++;
	    j--;
	}
	return i;
    }
    static void sort (int[] a, int left, int right) {
	if (left < right) {
	    int q = partition(a, left, right);
	    sort(a, left, q-1);
	    sort(a, q+1, right);
	}
    }
    static int findmiddle (int[] array, int left, int right) {
	int a = array[left];
	int b = array[(left+right) / 2];
	int c = array[right];
	if (a <= b) {
	    if (c < a) return left;
	    else if (b < c) return (left + right)/2;
	    else return right;
	}
	else { // a > b
	    if (c < b) return left;
	    else if (a < c) return (left + right)/2;
	    else return right;
	}
    }
}