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.*;
import java.io.*;

class Main {

	static class Data {
		int point;
		int data;
	}

	static final Comparator<Data> COMPARATOR = new Comp();

	static class Comp implements Comparator<Data> {
		public int compare(Data x,Data y){
			if (x.data > y.data)
				return 1;
			else if(x.data < y.data)
				return -1;
			else
				return 0;
		}
	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		String s = br.readLine();

		String[] str = s.split(" ");
		Data[] w = new Data[n];
		PriorityQueue<Data> pq = new PriorityQueue<Data>(10,COMPARATOR);

		for (int i=0; i<n; i++) {
			w[i] = new Data();
			w[i].data = Integer.parseInt(str[i]);
			pq.add(w[i]);
		}

		for (int i=0; i<n; i++) {
			pq.poll().point = i;
		}


		int count = 0;
		int sum = 0;

		while (count < n) {
			boolean flag = false;
			for (int i=0; i<n; i++) {
				if (w[i].point == count) {
					flag = true;
					if (w[i].point == i) {
						count++;
						break;
					}
					for (int j=0; j<n; j++) {
						if (w[j].point == i) {
							sum += w[i].data + w[j].data;
							w[j].point = w[i].point;
							w[j].data = w[i].data;
							w[i].point = -1;
							flag = false;
							break;
						}
					}
					if (!flag) {
						flag = true;
						break;
					}
				}
			}
			if (!flag) {
				count++;
			}
		}

		System.out.println(sum);

		br.close();
	}
}