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;
template <typename T>
class Array {
 private:
  void merge(int l, int m, int r) {
    int n1 = m - l;
    int n2 = r - m;
    vector<T> L, R;
    L.resize(n1 + 1);
    R.resize(n2 + 1);
    for (int i = 0; i < n1; i++) L[i] = A[l + i];
    for (int i = 0; i < n2; i++) R[i] = A[m + i];
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    int a = 0;
    int b = 0;
    for (int i = l; i < r; i++) {
      if (L[a] <= R[b]) {
        A[i] = L[a];
        a++;
      } else {
        A[i] = R[b];
        b++;
      }
    }
  }
  int partition(int p, int r) {
    T x = A[r];
    int i = p - 1;
    T tmp;
    for (int j = p; j < r; j++) {
      if (A[j] <= x) {
        i++;
        tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
      }
    }
    tmp = A[i + 1];
    A[i + 1] = A[r];
    A[r] = tmp;
    return i + 1;
  }

 public:
  Array();
  Array(vector<T> &arr) { A = arr; }
  vector<T> A;
  T operator[](int x) { return A[x]; }
  void dispArr() {
    for (int i = 0; i < A.size() - 1; i++) cout << A[i] << " ";
    cout << A[A.size() - 1] << endl;
  }
  void swap(int i, int j) {
    T tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
  }
  void mergeSort(int l, int r) {
    if (l + 1 < r) {
      int m = (l + r) / 2;
      mergeSort(l, m);
      mergeSort(m, r);
      merge(l, m, r);
    }
  }
  void quicksort(int p, int r) {
    if (p < r) {
      int q = partition(p, r);
      quicksort(p, q - 1);
      quicksort(q + 1, r);
    }
  }
};
int main() {
  int n;
  cin >> n;
  vector<int> v;
  v.resize(n);
  for (int i = 0; i < n; i++) cin >> v[i];
  Array<int> x(v);
  Array<int> y(v);
  y.mergeSort(0, n);
  int cnt = 0;
  int cost = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (x[i] != y[i]) {
      for (int j = i; j >= 0; j--) {
        if (x[i] == y[j]) {
          x.swap(i, j);
          cost += (x[i] + x[j]);
          break;
        }
      }
    }
  }
  cout << cost << endl;
  return 0;
}
