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;
int g_cost = 0;
void swap(int array[], int i0, int i1) {
  int temp = array[i1];
  array[i1] = array[i0];
  array[i0] = temp;
}
inline bool isSortedAtIndex(int idx, const int array0[], const int array1[]) {
  return array0[idx] == array1[idx];
}
int getIdxOf(int num, const int array[], int numOfArray) {
  for (int i = 0; i < numOfArray; i++) {
    if (array[i] == num) return i;
  }
  const int error = -1;
  return error;
}
void calculateCost(int idx, int numOfArray, const int array[],
                   const int sortedArray[], int &swapIdx, float &cost) {
  const int targetNum = sortedArray[idx];
  swapIdx = getIdxOf(targetNum, array, numOfArray);
  cost = static_cast<float>(array[idx] + array[swapIdx]);
  if (sortedArray[swapIdx] == array[idx]) cost /= 2.f;
  ;
}
int main() {
  int numOfArray;
  cin >> numOfArray;
  cin.ignore();
  int array[numOfArray];
  for (int i = 0; i < numOfArray; i++) cin >> array[i];
  int sortedArray[numOfArray];
  for (int i = 0; i < numOfArray; i++) sortedArray[i] = array[i];
  sort(sortedArray, sortedArray + numOfArray);
  {
    bool needSort = true;
    do {
      needSort = false;
      float minCost = FLT_MAX;
      pair<int, int> swapIndcies = make_pair(-1, -1);
      for (int i = 0; i < numOfArray; i++) {
        if (isSortedAtIndex(i, array, sortedArray)) continue;
        needSort = true;
        int swapIdx;
        float cost;
        calculateCost(i, numOfArray, array, sortedArray, swapIdx, cost);
        if (minCost > cost) {
          minCost = cost;
          swapIndcies = make_pair(i, swapIdx);
        }
      }
      if (needSort) {
        ;
        swap(array, swapIndcies.first, swapIndcies.second);
        g_cost += array[swapIndcies.first] + array[swapIndcies.second];
      }
    } while (needSort);
  }
  cout << g_cost << endl;
  return 0;
}
