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;
void show_mincost(int arr[], size_t arr_s, int swap_l_val, int swap_r_val) {
  cout << arr[0] << flush;
  for (size_t i = 1; i < arr_s; i++) {
    if (arr[i] == swap_l_val || arr[i] == swap_r_val) {
      cout << "(" << arr[i] << ')';
    } else {
      cout << ' ' << arr[i] << ' ';
    }
  }
  cout << ' ' << "COST : " << swap_l_val << " + " << swap_r_val
       << " == " << swap_l_val + swap_r_val << endl;
}
void show(int arr[], size_t size) {
  cout << arr[0] << flush;
  for (size_t i = 1; i < size; i++) {
    cout << ' ' << arr[i] << flush;
  }
  cout << endl;
}
int merge(int arr[], unsigned int arr_s, unsigned int lft, unsigned int md,
          unsigned int rgt) {
  int cnt = 0;
  int left_s = md - lft + 1, right_s = rgt - md + 1, *left = new int[left_s],
      *right = new int[right_s];
  for (int i = 0; i < left_s - 1; i++) {
    left[i] = arr[lft + i];
  }
  left[left_s - 1] = INT_MAX;
  for (int i = 0; i < right_s - 1; i++) {
    right[i] = arr[md + i];
  }
  right[right_s - 1] = INT_MAX;
  for (int i = 0, left_i = 0, right_i = 0; i < left_s + right_s - 2;
       i++, cnt++) {
    if (left[left_i] <= right[right_i]) {
      arr[lft + i] = left[left_i];
      ++left_i;
    } else {
      arr[lft + i] = right[right_i];
      ++right_i;
    }
  }
  delete[] right;
  delete[] left;
  return cnt;
}
int mergeSort(int arr[], unsigned int arr_s, unsigned int lft,
              unsigned int rgt) {
  static int cnt = 0;
  unsigned int md = (lft + rgt) / 2;
  if (rgt - lft >= 2) {
    mergeSort(arr, arr_s, lft, md);
    mergeSort(arr, arr_s, md, rgt);
    cnt += merge(arr, arr_s, lft, md, rgt);
  }
  return cnt;
}
size_t idxKey(int arr[], size_t arr_s, int key) {
  for (size_t i = 0; i != arr_s; i++) {
    if (arr[i] == key) return i;
  }
  return arr_s;
}
unsigned int minCost(int arr[], size_t arr_s) {
  int *sorted = new int[arr_s];
  for (size_t i = 0; i < arr_s; i++) {
    sorted[i] = arr[i];
  }
  mergeSort(sorted, arr_s, 0, arr_s);
  show(sorted, arr_s);
  unsigned int cost = 0;
  int swap_l_val, swap_l_idx, swap_r_val, swap_r_idx;
  for (size_t i = 0;;) {
    while (idxKey(arr, arr_s, sorted[i]) == i) {
      i++;
    }
    swap_l_idx = idxKey(arr, arr_s, sorted[i]);
    swap_r_idx = idxKey(arr, arr_s, sorted[idxKey(arr, arr_s, sorted[i])]);
    if (swap_l_idx == swap_r_idx) break;
    swap_l_val = arr[swap_l_idx];
    swap_r_val = arr[swap_r_idx];
    swap(arr[idxKey(arr, arr_s, sorted[i])],
         arr[idxKey(arr, arr_s, sorted[idxKey(arr, arr_s, sorted[i])])]);
    cost += swap_l_val + swap_r_val;
    show_mincost(arr, arr_s, swap_l_val, swap_r_val);
  }
  return cost;
}
int main() {
  size_t arr_s;
  cin >> arr_s;
  int *arr = new int[arr_s];
  for (size_t i = 0; i < arr_s; i++) {
    cin >> arr[i];
  }
  long long mincst = minCost(arr, arr_s);
  cout << mincst << endl;
}
