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;
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;
    if (minall > a[i].num) {
      minall = a[i].num;
    }
  }
  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 + minall + cnt * mini);
    }
  }
  printf("%d\n", sol);
  return 0;
}
