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>
int cost;
void swap(int *, int, int);
void Quicksort(int *, int, int);
int Partition(int *, int, int);
int main() {
  int W[1000], W2[1000], i, j, n;
  int min = 100000000;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &W[i]);
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) W2[j] = W[j];
    swap(W2, i, n - 1);
    cost = 0;
    Quicksort(W2, 0, n - 1);
    if (cost < min) min = cost;
  }
  printf("%d\n", cost);
}
void swap(int *n, int p, int q) {
  int box;
  box = n[p];
  n[p] = n[q];
  n[q] = box;
}
void Quicksort(int *n, int p, int r) {
  int q;
  if (p < r) {
    q = Partition(n, p, r);
    Quicksort(n, p, q - 1);
    Quicksort(n, q + 1, r);
  }
}
int Partition(int *n, int p, int r) {
  int i, j, x;
  x = n[r];
  j = p - 1;
  for (i = p; i < r; i++) {
    if (n[i] <= x) {
      j++;
      swap(n, j, i);
    }
  }
  if (j + 1 != r) cost += (n[j + 1] + n[r]);
  swap(n, j + 1, r);
  return j + 1;
}
