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 <queue>
#include <unordered_map>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

namespace std{
	template<typename T>
	inline void hash_combine(size_t& seed, T const& v){
		seed ^= hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
	}
    template<typename It>
    inline size_t hash_range(It first, It last){
		size_t seed=0;
		hash_range(seed,first,last);
		return seed;
	}
	template<typename It>
	inline void hash_range(size_t& seed, It first, It last){
		for(;first!=last;++first)hash_combine(seed, *first);
	}
	template<typename A,typename B>
	class hash<pair<A,B>>{
		public:
		size_t operator()(pair<A,B> const &p) const{
			size_t seed=0;
			hash_combine(seed,p.first);
			hash_combine(seed,p.second);
			return seed;
		}
	};
	template<typename T,size_t N>
	class hash<array<T,N>>{
		public:
		size_t operator()(array<T,N> const &container) const{
			return hash_range(container.begin(),container.end());
		}
	};
	template<typename T,typename A>
	class hash<vector<T,A>>{
		public:
		size_t operator()(vector<T,A> const &container) const{
			return hash_range(container.begin(),container.end());
		}
	};
}

int main(){
	int N;
	scanf("%d",&N);
	vector<short>v(N);
	for(int i=0;i<N;i++)scanf("%d",&v[i]);
	priority_queue<pair<int,vector<short> > >q;
	unordered_map<vector<short>,int>depth;

	q.push(make_pair(0,v));
	int R;
	for(;!q.empty();){
		pair<int,vector<int> >cur=q.top();
		q.pop();
		if(depth.find(cur.second)!=depth.end())continue;
		depth[cur.second]=cur.first;
		bool f=false;
		for(int i=0;i<N;i++)for(int j=0;j<N;j++)if(i!=j&&cur.second[i]>cur.second[j]){
			if(i<j)f=true;
			swap(cur.second[i],cur.second[j]);
			q.push(make_pair(cur.first-cur.second[i]-cur.second[j],cur.second));
			swap(cur.second[i],cur.second[j]);
		}
		if(!f){
			R=-cur.first;
			break;
		}
	}
	printf("%d\n",R);
}