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>
const int MAX_N = 1000;
long swap(std::vector<int> *A, int i, int j) {
  int tmp = A->at(i);
  A->at(i) = A->at(j);
  A->at(j) = tmp;
  return A->at(i) + A->at(j);
}
int partition(std::vector<int> *A, int left, int right, int pivot,
              int *weight) {
  int l = left;
  int r = right;
  while (l <= r) {
    while ((l <= right) && (A->at(l) < pivot)) {
      l++;
    }
    while ((r >= left) && (A->at(r) > pivot)) {
      r--;
    }
    if (l >= r) {
      break;
    }
    (*weight) += swap(A, l, r);
    l++;
    r--;
  }
  return l;
}
void print_array(std::vector<int> *A, int left, int right) {
  for (int i = left; i <= right; i++) {
    std::cout << A->at(i) << " ";
  }
  std::cout << std::endl;
}
long quick_sort(std::vector<int> *A, int left, int right) {
  if (left >= right) {
    return 0;
  }
  std::vector<int> *O = new std::vector<int>();
  O->reserve(MAX_N);
  for (int i = left; i <= right; i++) {
    O->push_back(A->at(i));
  }
  long minWeight = LONG_MAX;
  for (int i = left + 1; i < right; i++) {
    int weight = 0;
    int q = partition(A, left, right, A->at(i), &weight);
    weight += quick_sort(A, left, q - 1);
    weight += quick_sort(A, q + 1, right);
    if (weight < minWeight) {
      minWeight = weight;
    }
    for (int j = left; j <= right; j++) {
      A->at(j) = O->at(j - left);
    }
  }
  if (minWeight == LONG_MAX) {
    minWeight = 0;
  }
  return minWeight;
}
int main(void) {
  std::ios_base::sync_with_stdio(false);
  int n = 0;
  std::cin >> n;
  std::vector<int> *A = new std::vector<int>();
  A->reserve(MAX_N);
  for (int i = 0; i < n; i++) {
    int w = 0;
    std::cin >> w;
    A->push_back(w);
  }
  long weight = quick_sort(A, 0, A->size() - 1);
  std::cout << weight << std::endl;
  return 0;
}
