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

using namespace std;

typedef long long lli;
typedef vector<lli> vll;

lli n;
vll w;
vll w_;
lli ans = 0;
lli mini;


int main(){
	cin >> n;
	w = vll(n);
	w_ = vll(n);
	for(lli i = 0;i < n;i++) cin >> w[i];
	for(lli i = 0;i < n;i++) w_[i] = i;
	sort(w_.begin(),w_.end(),[](lli a,lli b){
		return w[a] < w[b];
	});
	mini = w[w_[0]];
	for(lli i = 0;i < n;i++){
		lli ans_ = 0,c = 0;
		while(w_[i] != i){
			ans_ += w[w_[i]] + w[w_[w_[i]]];
			swap(w[w_[i]],w[w_[w_[i]]]);
			swap(w_[i],w_[w_[i]]);
			c++;
		}
		if(c*(w[i]-mini) > 2*(w[i]+mini)){
			ans_ -= c*(w[i]-mini) - 2*(w[i]+mini);
		}
		ans += ans_;
	}
	cout << ans << endl;
	return 0;
}