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>
int32_t merge(vector<T> &A, int32_t left, int32_t mid, int32_t right) {
  int32_t n1 = mid - left;
  int32_t n2 = right - mid;
  vector<T> L(n1 + 1);
  vector<T> R(n2 + 1);
  for (int32_t i = 0; i < n1; i++) {
    L[i] = A[left + i];
  }
  for (int32_t i = 0; i < n2; i++) {
    R[i] = A[mid + i];
  }
  L[n1] = INT32_MAX;
  R[n2] = INT32_MAX;
  int32_t i = 0, j = 0, count = 0;
  for (int32_t k = left; k < right; k++) {
    if (L[i] <= R[j]) {
      A[k] = L[i];
      i++;
    } else {
      A[k] = R[j];
      j++;
    }
    count++;
  }
  return count;
}
template <typename T>
int32_t merge_sort(vector<T> &A, int32_t left, int32_t right) {
  if (left + 1 < right) {
    int32_t mid = left + (right - left) / 2;
    int32_t count1 = merge_sort(A, left, mid);
    int32_t count2 = merge_sort(A, mid, right);
    int32_t count3 = merge(A, left, mid, right);
    return count1 + count2 + count3;
  }
  return 0;
}
template <typename T>
int32_t cost(const vector<T> &unsorted, const vector<T> &sorted,
             map<vector<int32_t>, int32_t> &mp) {
  bool is_sorted = true;
  int32_t c = INT32_MAX;
  for (int32_t i = 0; i < unsorted.size(); i++) {
    if (unsorted[i] != sorted[i]) {
      is_sorted = false;
      int32_t j = 0;
      while (unsorted[i] != sorted[j]) j++;
      vector<T> unsorted2(unsorted);
      swap(unsorted2[i], unsorted2[j]);
      auto itr = mp.find(unsorted2);
      int32_t c2;
      if (itr != mp.end()) {
        c2 = itr->second;
      } else {
        c2 = unsorted2[i] + unsorted2[j] + cost(unsorted2, sorted, mp);
        mp[unsorted2] = c2;
      }
      c = min(c, c2);
    }
  }
  return (is_sorted ? 0 : c);
}
int main() {
  int32_t n;
  cin >> n;
  vector<int32_t> w1(n);
  for (int32_t i = 0; i < n; i++) {
    cin >> w1[i];
  }
  vector<int32_t> w2(w1);
  merge_sort(w2, 0, n);
  map<vector<int32_t>, int32_t> mp;
  cout << cost(w1, w2, mp) << endl;
  return 0;
}
