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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {
	public static void main(String[] args) throws IOException {
		// Input an array
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
	
		Baggage[] a = new Baggage[n];
		String[] strs = br.readLine().split(" ");
	    for(int i = 0; i < n; ++i){
	        a[i] = new Baggage(i, Integer.parseInt(strs[i]));
	    }
	    
	    // Number the array
	    mergeSort(a, 0, n);
	    
	    // Calc. cost
	    int cost = 0;
	    int minw = a[0].weight;
	    int loss, cnt, j;
	    for(int i = 0; i < n; ++i) {
	    	if(a[i].flag == true){
		    	// search group key i
	    		continue;
	    	}
    		
	    	// count cost for group i
	    	cnt = 0; // swap count
	    	j = a[i].org;
	    	while(j != i) {
	    		// swap a[j] and a[i]
	    	    cost += a[j].weight + a[i].weight;
	    		cnt += 1;

	    	    a[j].flag = true;
		    	j = a[j].org;
	   	    }
	    	loss = (a[i].weight * cnt) - minw * cnt - 2 * (minw + a[i].weight);
	    	if(loss > 0){
	    		cost -= loss;
	    	}
	    }
	    
	    System.out.println(cost);
	}
	
	public static void mergeSort(Baggage[] s, int left, int right) {
		if(left + 1 < right) {
			int mid = (left + right) / 2;
			mergeSort(s, left, mid);
			mergeSort(s, mid, right);
			merge(s, left, mid, right);
		}
	}
	public static void merge(Baggage[] s, int left, int mid, int right) {
		Baggage[] s1 = Arrays.copyOfRange(s, left, mid + 1);
		Baggage[] s2 = Arrays.copyOfRange(s, mid, right + 1);
		
		s1[mid - left] = new Baggage(-1, Integer.MAX_VALUE);
		s2[right - mid] = new Baggage(-1, Integer.MAX_VALUE);
		int i = 0;
		int j = 0;
		for(int k = left; k < right; ++k) {
			if(s1[i].weight <= s2[j].weight){
				s[k] = s1[i];
				i += 1;
			}else{
				s[k] = s2[j];
				j += 1;
			}
		}
		
	}
}

class Baggage {
	public int org;
	public int weight;
	public boolean flag;
	public Baggage(int o, int w) {
		org = o;
		weight = w;
		flag = false;
	}
}