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
#include <bits/stdc++.h>
using namespace std;
#define N 1002

int A[N], B[N], C[N];
int minValue;
long cnt;

struct circleX {
	int n;
	int sum;
	int minOfThis;
	circleX() {
		clear();
	}
	void clear() {
		n = 0;
		sum = 0;
		minOfThis = INT_MAX;
	}
};

int main(void) {
	cnt = 0;
	int n, i, index;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> A[i];
		B[i] = A[i];
		C[i] = 0;
	}
	sort(B, B + n);
	minValue = B[0];
	circleX cir;
	int *p;
	for (i = 0; i < n; i++) {
		index = i;
		cir.clear();
		while (C[index] == 0) {
			C[index] = 1;
			cir.n++;
			cir.sum += A[index];
			cir.minOfThis = min(cir.minOfThis, A[index]);
			p = lower_bound(B, B + n, A[index]);
			index = distance(B, p);
		}
		if (cir.n > 1) {
			int x1 = (cir.sum + (cir.n - 2) * cir.minOfThis);
			int x2 = (cir.sum + cir.minOfThis + (cir.n + 1) * minValue);
			if (x1 <= x2)
				cnt += x1;
			else 
				cnt += x2;
		}
	}
	cout << cnt << endl;
}
