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 A[1000], SortA[1000], Type[1000], NoT[1000] = {}, NNot = 0;
int Typesum_min[1000][2];
bool Complete[1000] = {};
int MIN;
void typing(int type, int iro) {
  while (!Complete[type]) {
    Type[type] = iro;
    Typesum_min[iro][0] += A[type];
    if (Typesum_min[iro][1] > A[type]) {
      Typesum_min[iro][1] = A[type];
    }
    NoT[iro]++;
    Complete[type] = true;
    type = SortA[type];
  }
}
void DecideType(int n) {
  int T = 0;
  for (int i = 0; i < n; i++) {
    if (!Complete[i]) {
      typing(i, T);
      Typesum_min[i][0] -= Typesum_min[i][1];
      NNot++;
      T++;
    }
  }
}
void solve() {
  int SSum = 0;
  for (int i = 0; i < NNot; i++) {
    if (NoT[i] == 1) {
    } else if (MIN * (NoT[i] - 1) + 2 * (Typesum_min[i][1] + MIN) >=
               Typesum_min[i][1] * (NoT[i] - 1)) {
      SSum += Typesum_min[i][0] + Typesum_min[i][1] * (NoT[i] - 1);
    } else {
      SSum += Typesum_min[i][0] + MIN * (NoT[i] - 1) +
              2 * (Typesum_min[i][1] + MIN);
    }
  }
  printf("%d\n", SSum);
}
int main() {
  priority_queue<pair<int, int> > PQ;
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &A[i]);
    PQ.push(make_pair(-A[i], i));
    Typesum_min[i][0] = 0;
    Typesum_min[i][1] = 2000000000;
  }
  for (int i = 0; i < n; i++) {
    SortA[i] = PQ.top().second;
    PQ.pop();
  }
  MIN = A[SortA[0]];
  DecideType(n);
  solve();
  return 0;
}
