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>
void CountingSort(const std::vector<int>& A, std::vector<int>& B, int k) {
  std::vector<int> C(k + 1, 0);
  for (int j = 0; j < A.size(); ++j) {
    C[A[j]]++;
  }
  for (int i = 1; i <= k; ++i) {
    C[i] = C[i] + C[i - 1];
  }
  for (int j = 0; j < A.size(); ++j) {
    B[C[A[j]] - 1] = A[j];
    C[A[j]]--;
  }
}
int GetCost(const std::vector<int>& Source, const std::vector<int>& Sorted) {
  int Cost = 0;
  assert(Source.size() == Sorted.size());
  std::vector<int> List = Source;
  for (int i = (int)Sorted.size() - 1; i >= 0; --i) {
    std::vector<int>::iterator It =
        std::find(List.begin(), List.end(), Sorted.at(i));
    assert(It != List.end());
    if (std::distance(List.begin(), It) == i) continue;
    Cost += *It + *(List.begin() + i);
    std::swap(*It, *(List.begin() + i));
  }
  return Cost;
}
int main() {
  int n;
  std::cin >> n;
  std::vector<int> A(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> A[i];
  }
  int k = *std::max_element(A.begin(), A.end());
  std::vector<int> B(n);
  CountingSort(A, B, k);
  std::cout << GetCost(A, B) << std::endl;
  return 0;
}
