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

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO ?????????????????????????????????????????????
		BufferedReader br =
				new BufferedReader( new InputStreamReader(System.in) );
		int n = Integer.parseInt( br.readLine() );

		String[] str = br.readLine().split(" ");
		Bag[] preW = new Bag[n]; // ??´????????????????????? w_i ?????\????????????
		Bag[] postW = new Bag[n]; // ??´??????????????????????????\????????????
		for (int i=0; i < n; i++) {
			preW[i] = new Bag( Integer.parseInt(str[i]), i );
			postW[i] = preW[i];
		}

		Arrays.sort(postW);
		for (int i=0; i < n; i++) {
			postW[i].posti = i;
		}

		/*
		 * 5, 4, 1, 3, 2, : W  pre
		 *
		 *                  W[0] = 5
		 *  , 4, 1, 3, 2, : bag = 5, nextbag = 2,
		 *             5,
		 *
		 *  , 4, 1, 3, 5, : bag = 2, nextbag = 4,
		 *    2,
		 *
		 *  , 2, 1, 3, 5, : bag = 4, nextbag = 3,
		 *          4,
		 *
		 *  , 2, 1, 4, 5, : bag = 3, nextbag = 1,
		 *       3,
		 *
		 *  , 2, 3, 4, 5, : bag = 1, nextbag = 5,
		 * 1,
		 *                  bag = 5,
		 *                  bag.prei = 0
		 *
		 * 1, 2, 3, 4, 5, : orderedW  post
		 */

		Bag bag, nextbag;
		int count;
		int ans = 0;
		int least = postW[0].wei;
		for (int i=0; i < n; i++) {
			bag = postW[i];
			if (bag.label == true) continue;
			if (bag.prei == bag.posti) continue;

			bag.label = true;
			count = 0;
			int mini = bag.wei;
			while (true) {
				nextbag = preW[bag.posti]; // nextbag.prei == bag.posti
				if (nextbag == postW[i]) break; // postW[i] ??????????????¨??????nextbag????????£??????????????????postW[i]????????£????????????
				nextbag.label = true;
				count++;
				ans += nextbag.wei;
				bag = nextbag;
			}
			int nochange = mini * count;
			int change = (least+mini)*2 + least*count;
			ans += Math.min(change, nochange);
		}

		System.out.println(ans);
	}

	static class Bag implements Comparable<Bag> {
		int wei; // weight

		int prei; // pre index ??´?????????????????????????????????

		int posti; // post index ??´??????????????¨?????????????????????

		boolean label = false;

		Bag(int w, int i) {
			this.wei= w;
			this.prei = i;
		}

//		Bag next(Bag[] preW, Bag[] postW) {
//			int index = this.posti;
//			return preW[index];
//		}

		@Override
		public int compareTo(Bag b) {
			return this.wei - b.wei;
		}

		@Override
		public String toString() {
			return "" + wei;
		}
	}
}