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 W[1000];
int N;
int Compare(const void *a, const void *b) { return *(int *)a - *(int *)b; }
void Swap(int idx1, int idx2) {
  int tmp = W[idx1];
  W[idx1] = W[idx2];
  W[idx2] = tmp;
}
int SearchIdx(int wi) {
  for (int i = 0; i < N; i++) {
    if (W[i] == wi) {
      return i;
    }
  }
  return -1;
}
int main(void) {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> W[i];
  }
  int cost = 0;
  int w2[1000];
  memcpy(w2, W, sizeof(int) * N);
  qsort(w2, N, sizeof(int), Compare);
  for (int i = 0; i < N; i++) {
    int idx1 = SearchIdx(w2[i]);
    while (idx1 != i) {
      int idx2 = SearchIdx(w2[idx1]);
      Swap(idx1, idx2);
      cost = cost + W[idx1] + W[idx2];
      idx1 = idx2;
    }
  }
  cout << cost << "\n";
  return 0;
}
