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>
int n, cost;
int A[1001], B[1001];
int L[501], R[502];
void merge(int left, int mid, int right) {
  int i, j, n1 = mid - left, n2 = right - mid;
  for (i = 0; i < n1; i++) L[i] = A[left + i];
  L[n1] = INT_MAX;
  for (i = 0; i < n2; i++) R[i] = A[mid + i];
  R[n2] = INT_MAX;
  int l = 0, r = 0;
  for (i = left; i < right; i++) {
    if (L[l] <= R[r]) {
      A[i] = L[l];
      l++;
    } else {
      A[i] = R[r];
      r++;
    }
  }
}
void m_sort(int left, int right) {
  int mid;
  if (left + 1 >= right) return;
  mid = (left + right) / 2;
  m_sort(left, mid);
  m_sort(mid, right);
  merge(left, mid, right);
}
void swap(int a, int b, int *C) {
  int swap;
  swap = C[a];
  C[a] = C[b];
  C[b] = swap;
}
int min_search(int *C) {
  int res = n, i;
  C[n] = INT_MAX;
  for (i = 0; i < n; i++) {
    if (A[i] != C[i]) {
      if (C[res] > C[i]) res = i;
    }
  }
  return res;
}
int quest(int *C, int num, int jud, int nokorii) {
  int D[1001], E[1001], i, x, ans, ans2, judd, nokori;
  if (jud == n)
    x = min_search(C);
  else
    x = jud;
  if (x == n) return num;
  for (i = 0; i < n; i++) {
    D[i] = C[i];
    E[i] = C[i];
  }
  i = 0;
  while (1) {
    if (D[i] == A[x]) {
      swap(i, x, D);
      nokori = nokorii - 1;
      judd = i;
      if (D[i] == A[i]) {
        judd = n;
        nokori--;
      }
      ans = quest(D, num + D[i] + D[x], judd, nokori);
      break;
    }
    i++;
  }
  if (E[x] != A[0] && nokorii >= 8) {
    swap(0, x, E);
    nokori = nokorii + 2;
    ans2 = quest(E, num + E[0] + E[x], x, nokori);
    if (ans > ans2) ans = ans2;
  }
  return ans;
}
int main() {
  scanf("%d", &n);
  int nokori = n;
  int i, j, min = n;
  for (i = 0; i < n; i++) {
    scanf("%d", &A[i]);
    B[i] = A[i];
  }
  m_sort(0, n);
  for (i = 0; i < n; i++) {
    if (A[i] == B[i]) nokori--;
  }
  cost = 0;
  for (i = 0; i < n; i++) {
    for (j = i + 1; j < n; j++) {
      if (B[i] == A[j]) {
        if (B[j] == A[i]) {
          swap(i, j, B);
          nokori -= 2;
          cost += B[i] + B[j];
        }
        break;
      }
    }
  }
  while (1) {
    if (min == n) min = min_search(B);
    if (B[min] != A[0]) {
      break;
    } else {
      if (min == n) break;
      for (i = 0; i < n; i++) {
        if (A[min] == B[i]) {
          if (min == i) {
            min = n;
            break;
          }
          swap(min, i, B);
          nokori--;
          cost += B[min] + B[i];
          min = i;
          break;
        }
      }
    }
  }
  cost = quest(B, cost, n, nokori);
  printf("%d\n", cost);
  return 0;
}
