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 <bits/stdc++.h>

using namespace std;

#define MAX 1000
#define MAX_D 10001

int main(){
  int N, arr[MAX], _arr[MAX], dest[MAX_D];
  bool used[MAX];

  cin >> N;
  for(int i = 0 ; i < N ; i++){
    cin >> arr[i];
    used[i] = false;
    _arr[i] = arr[i];
  }
  sort(_arr, _arr+N);

  for(int i = 0 ; i < N ; i++){
    dest[_arr[i]] = i;
  }

  int ans = 0;
  for(int i = 0 ; i < N ; i++){
    if(dest[arr[i]] == i || used[i]){
      used[i] = true;
      continue;
    }

    int cnt = -1, sum = 0, min = arr[i], next = i;
    for( ; !used[next] ; ){
      sum += arr[next]; cnt++;
      min = std::min(min, arr[next]);
      used[next] = true;
      next = dest[arr[next]];
    }
    sum -= min;
    ans += sum + min*cnt;

    if(2*(min+_arr[0]) < (min-_arr[0])*cnt){
      ans -= (min-_arr[0])*cnt - 2*(min+_arr[0]);
    }
  }

  cout << ans << endl;

  return 0;
}