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 <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	// step #1. input
	int N;
	cin >> N;
	vector<int> w(N);
	for(int i = 0; i < N; ++i) {
		cin >> w[i];
	}
	// step #2. make functional graph
	vector<int> p(N);
	for(int i = 0; i < N; ++i) {
		p[i] = i;
	}
	sort(p.begin(), p.end(), [&](int i, int j) { return w[i] < w[j]; });
	// step #3. calculate minimum cost
	int lightest = w[p[0]];
	vector<bool> vis(N, false);
	int ans = 0;
	for(int i = 0; i < N; ++i) {
		if(vis[i]) continue;
		int pos = i, sum = 0, sz = 0, sublight = w[pos];
		while(!vis[pos]) {
			sublight = min(sublight, w[pos]);
			sum += w[pos];
			++sz;
			vis[pos] = true;
			pos = p[pos];
		}
		int costA = sum + sublight * (sz - 2);
		int costB = sum + sublight + lightest * (sz + 1);
		ans += min(costA, costB);
	}
	cout << ans << endl;
	return 0;
}
