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 <algorithm>
using namespace std;
static const int VMAX = 10000;
int solve(int* arr, int len){
  int ans = 0, tmin = VMAX;
  int* narr = new int[len];
  int pos[VMAX+1];
  int* marked = new int[len];
  for(int i=0;i<len;i++){
    narr[i] = arr[i];
    marked[i] = 0;
    (arr[i]<tmin)?(tmin=arr[i]):(tmin);
  }
  sort(narr,narr+len);
  // record the position of values in sorted array
  for(int i=0;i<len;i++)
    pos[narr[i]]=i;
  // check the cycle of transform
  for(int i=0;i<len;i++){
    if(marked[i]==0){
      int sum = 0, min = VMAX, n = 0;
      for(int j = i; marked[j]==0 ; j = pos[arr[j]]){
        marked[j] = 1;
        n++;
        sum+=arr[j];
        (arr[j]<min)?(min = arr[j]):(min);
      }
      int a = sum + (n-2)*min;
      int b = sum + (n+1)*tmin + min;
      ans += (a<b)?a:b;
    }
  }
  delete[] narr;
  delete[] marked;
  return ans;
}

int main(){
  int len;
  cin >> len;
  int* arr = new int[len];
  for(int i=0;i<len;i++)
    cin>>arr[i];
  cout << solve(arr,len) << endl;
  delete[] arr;
  return 0;
}

