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;
}
int findIndexOf(int val, const int array[], int numOfArray) {
  for (int i = 0; i < numOfArray; i++)
    if (array[i] == val) return i;
  assert(0);
  return -1;
}
int calcCostSimple(const int array[], const vector<int> &l) {
  int s = 0;
  int minimum = INT_MAX;
  for (uint32_t i = 0; i < l.size(); i++) {
    int idx = l[i];
    s += array[idx];
    minimum = min(minimum, array[idx]);
  };
  return s + minimum * (l.size() - 2);
}
int calcCostSwap(const int array[], const vector<int> &l, int x) {
  if (array == nullptr || l.size() < 1 || x < 0) {
    assert(1);
    return INT_MAX;
  }
  int s = 0;
  int minimum = INT_MAX;
  for (uint32_t i = 0; i < l.size(); i++) {
    int idx = l[i];
    s += array[idx];
    minimum = min(minimum, array[idx]);
  };
  return s + minimum + x * (l.size() - 1);
}
int findMinOutsideLoop(vector<int> indices, int max, const int sortedArray[]) {
  sort(indices.begin(), indices.end());
  for (int i = 0; i < max; i++)
    if (indices[i] != i) return sortedArray[i];
  return INT_MAX;
}
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 visited[numOfArray];
  fill(visited, visited + numOfArray, 0);
  vector<vector<int>> loops;
  for (int i = 0; i < numOfArray; i++) {
    if (visited[i]) continue;
    int idx = i;
    vector<int> loop;
    while (!visited[idx]) {
      loop.push_back(idx);
      visited[idx] = true;
      int num = array[idx];
      idx = findIndexOf(num, sortedArray, numOfArray);
    }
    loops.push_back(loop);
  }
  for (uint32_t i = 0; i < loops.size(); i++) {
    const vector<int> l = loops[i];
    if (l.size() < 2) continue;
    int costA, costB;
    costA = calcCostSimple(array, l);
    int x = findMinOutsideLoop(l, numOfArray, sortedArray);
    if (x == INT_MAX)
      costB = INT_MAX;
    else
      costB = calcCostSwap(array, l, x);
    g_cost += min(costA, costB);
    ;
  }
  cout << g_cost << endl;
  return 0;
}
