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;

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

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

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

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

	return j+1;
}

void quicksort(int *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 solve_swap(int *a,int *b,int n)
{
	int sum,temp;
	for(int i = 0; i < n; i++)
	{
		if (a[i] != b[i])
		{
			for(int j = i+1; j < n; j++)
			{
				if (b[j] == a[i] && b[i] == a[j])
				{
					temp = a[i];
					a[i] = a[j];
					a[j] = temp;

					sum += a[i] + a[j];
					break;
				}
			}
		}
	}

	return sum;
}

int solve1(int *a,int *b,int n)
{
	bool check;
	int min,num,temp,sum,start;

	sum = 0;
	start = 0;

	while(1)
	{
		min = INF;
		
		check = true;

		//printf("start = %d\n", start);

		for(int i = start; i < n; i++)
		{
			if (min > a[i] && a[i] != b[i])
			{
				num = i;
				min = a[num];
			}
		}

		//printf("num = %d\n", num);
		//printf("min = %d\n", min);

		for(int i = 0; i < n; i++)
		{
			if (a[i] == b[num])
			{
				//printf("%d and %d are swapped\n", a[num],a[i]);
				sum += a[num] + a[i];
				temp = a[i];
				a[i] = min; // min = a[num]
				a[num] = temp;
				num = i;
			}
		}

		for(int i = 0; i < n; i++)
		{
			if (a[i] != b[i])
			{
				check = false;
				start = i;
				break;
			}
		}

		for(int i = 0; i < n; i++)
		{
			//printf("a[i] = %d\n", a[i]);
		}

		if (check)
		{
			break;
		}

	}

	return sum;
}

bool check(int *A,int *B,int n)
{
	bool c = true;

	for(int i = 0; i < n; i++)
	{
		if (A[i] != B[i])
		{
			c = false;
		}
	}

	return c;
}

int main()
{
	int n,a[1000] = {0},b[1000] = {0},a2[1000] = {0};
	int sum1 = 0;
	//int sum2 = 0,pivot = 0,pivot1 = 0,pivot2= 0,min = 0,start=0,temp=0,k=0;

	scanf("%d", &n);

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

	quicksort(b,0,n-1);

	sum1 = solve_swap(a,b,n);

	//printf("sum = %d\n", sum1);

	if (check(a,b,n))
	{
		cout << sum1 <<endl;

		return 0	}

/*
	sum2 = sum1;

	for(int i = 0; i < n; i++)
	{
		a2[i] = a[i];
	}

	//printf("\nhere is sum1\n");

	sum1 += solve1(a,b,n);

	//printf("sum1 = %d\n",sum1);


	if (check(a,b,n))
	{
		printf("%d\n", sum1);
		return 0;
	}



	for(int i = 1; i < n - start; i++)
	{
		k = start;

		
		while(1)
		{
			if (b[pivot1] == a[k])
			{
				printf("%d and %d are swapped\n", a[pivot1],a[k]);
				temp = a[pivot1];
				a[pivot1] = a[k];
				a[k] = temp;

				sum1 += a[pivot1] + a[k];
				pivot1 = k;

				break;
			}
			k++;
		}

		for(int i = 0; i < n; i++)
		{
			printf("%d ", a[i]);
		}
		cout << endl;
	}


	if (!check(a,b,n))
	{
		printf("\nhere is sum2\n");
		temp = a2[pivot2];
		a2[pivot2] = a2[0];
		a2[0] = temp;

		for(int i = 1; i < n - start; i++)
		{
			int j = start;
			while(1)
			{
				if (b[pivot2] == a2[j])
				{
					printf("%d and %d are swapped\n", a2[pivot2],a2[j]);
					temp = a2[pivot2];
					a2[pivot2] = a2[j];
					a2[j] = temp;

					sum2 += a2[pivot2] + a2[j];
					pivot2 = j;

					break;
				}

				j++;
			}

			for(int i = 0; i < n; i++)
			{
				printf("%d ", a2[i]);
			}
			cout << endl;
		}


		if (sum1 < sum2)
		{
			printf("sum1 = %d\n", sum1);
		}else
		{
			printf("sum2 = %d\n", sum2);
		}

		return 0;
	}


	printf("%d\n", sum1);
*/

	return 0;
}
	