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
/*
 * ALDS1_6_D.cpp
 *
 *  Created on: May 2, 2018
 *      Author: 13743
 */

#include<iostream>
#include<algorithm>

using namespace std;

int main() {
	int n;
	int A[1000];
	int B[1000];
	int aW[10001] = {-1};
	cin >> n;
	for(int i=0; i<n; i++) {
		cin >> A[i];
		B[i] = A[i];
		aW[A[i]] = i;
	}

	sort(B, B+n);
	int glMin = B[0];
	int rm = 0;

	for(int i=0; i<n; i++) {
		if(aW[B[i]] == -1) continue;
		int c = 0;
		int lcMin = B[i];
		int j = aW[lcMin];
		aW[lcMin] = -1;
		rm -= lcMin;
		while(j != -1) {
			rm += A[j];
			c++;
			int a = B[j];
			j = aW[B[j]];
			aW[a] = -1;
		}
		rm += min(lcMin*(c-1), 2*(lcMin+glMin)+glMin*(c-1));
	}

	cout << rm << endl;
}



