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;
#define MAX 10000

int main(){
  int n;
  cin >> n;
  int tmp, w1[n+1], w2[n+1], idx[MAX+1], x = MAX, color[MAX+1];
  for ( int i = 0; i < n; i++){
    cin >> tmp ;
    w1[i] = w2[i] = tmp;
    x = min(x, tmp);
    color[i] = 0;
  }

  sort(w2, w2+n);
  for ( int i = 0; i < n; i++ ){
    idx[w2[i]] = i;
  }

  int aSum = 0;
  for ( int i = 0; i < n; i++){
    if ( w1[i] == w2[i] || color[i]) continue;
    int cur = i;
    int Min = w2[i], lSum = 0, lN = 0, nextCorrect = 0;;
    while( 1 ){
      color[cur] = 1;
      Min = min(Min, w2[cur]);
      lSum += w2[cur];
      lN ++;
      cur = idx[w1[cur]];
      if (color[cur]) break;
    }
    aSum += min( Min * (lN - 2) + lSum, x * (lN + 1) + Min + lSum );
  }

  cout << aSum << endl;

  return 0;
}
