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 <string>
#include <algorithm>
#include <cstdio>

using namespace std;

const int INF = 1000000;

struct node
{
	int num;
	int place;  
};

int partition(node *A,int p,int r)
{
	int j,temp;
	node x;

	x = A[r];
	j = p-1;

	for(int i = p; i < r; i++)
	{
		if (A[i].num <= x.num)
		{
			j++;
			temp = A[i].num;
			A[i].num = A[j].num;
			A[j].num = temp;
		}
	}

	temp = A[j+1].num;
	A[j+1].num = A[r].num;
	A[r].num = temp;

	return j+1;
}

void quicksort(node *A,int p,int r)
{
	int q;

	if (p < r)
	{
		q = partition(A,p,r);
		quicksort(A,p,q-1);
		quicksort(A,q+1,r);
	}
}


int main()
{
	int n,sum,minall,mini,sol,cnt,j;
	node a[1000] = {0},b[1000] = {0};

	sol = 0;
	minall = INF;

	scanf("%d", &n);

	for(int i = 0; i < n; i++)
	{
		scanf("%d", &a[i].num);
		a[i].place = i;
		b[i] = a[i];
		b[i].place = i;
	}

	quicksort(b,0,n-1);

	for(int i = 0; i < n; i++)
	{
		sum = 0;

		if (a[i].num >= 0)
		{
			sum += a[i].num;
			mini = a[i].num;
			cnt = 1;
			j = i;

			while(b[a[j].place].num != a[i].num)
			{
				for(int k = 0; k < n; k++)
				{
					if (a[k].num == b[a[j].place].num)
					{
						j = k;
						sum += a[k].num;
						cnt++;

						if (mini > a[k].num)
						{
							mini = a[k].num;
						}

						a[k].num = -1;
						break;
					}
				}
			}

			a[i].num = -1;

			sol += min(sum + mini * (cnt -2), sum + mini + (cnt + 1) * b[0]);
		}
	}

	printf("%d\n", sol);


	return 0;
}
	