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 <iostream>
#include <algorithm>

using namespace std;

int n;
int a[1005], b[1005], c[10005];
bool ifs[1005];
int mins = 10005;
long cost = 0;



int main() {
	long c1, c2, cmin;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		if (a[i] < mins) {
			mins = a[i];
		}
		b[i] = a[i];
		ifs[i] = false;
	}

	sort(b, b+n);
	for (int i = 0; i < n; ++i) {
		c[b[i]] = i;
	}
	
	for (int i = 0; i < n; ++i) {
		if (ifs[i]) {
			continue;
		}
		int j = i;
		int t = 0;
		c1  = 0;
		c2 = 0;
		cmin = a[j];
		while (1) {
			ifs[j] = true;
			c1 += a[j];
			t++;
			j = c[a[j]];
			if (cmin > a[j]) {
				cmin = a[j];
			}
			if (ifs[j]) break;
		}
		c2 = cmin + c1 + (t + 1) * mins;
		c1 = c1 + (t - 2)*cmin;
		cost += min(c1, c2);
	}

	cout << cost << endl;

	return 0;
}
