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;
typedef struct {
  int a;
  int b;
  int c;
} arr;
arr L[510], R[510];
int merge(arr a[], int l, int m, int r, char c) {
  int n1 = m - l;
  int n2 = r - m;
  for (int i = 0; i < n1; i++) {
    L[i] = a[l + i];
  }
  for (int i = 0; i < n2; i++) {
    R[i] = a[m + i];
  }
  int i = 0, j = 0;
  if (c == 'a') {
    L[n1].a = 100000;
    R[n2].a = 100000;
    for (int k = l; k < r; k++) {
      if (L[i].a <= R[j].a) {
        a[k] = L[i++];
      } else {
        a[k] = R[j++];
      }
    }
  } else {
    L[n1].c = 100000;
    R[n2].c = 100000;
    for (int k = l; k < r; k++) {
      if (L[i].c <= R[j].c) {
        a[k] = L[i++];
      } else {
        a[k] = R[j++];
      }
    }
  }
}
int mergeS(arr a[], int l, int r, char c) {
  if (l + 1 < r) {
    int m = (l + r) / 2;
    mergeS(a, l, m, c);
    mergeS(a, m, r, c);
    merge(a, l, m, r, c);
  }
}
int main() {
  int n, j = 1;
  cin >> n;
  arr a[1010];
  pair<long long, long long> c[1010];
  for (int i = 1; i <= n; cin >> a[i++].a)
    ;
  a[n + 1].a == 1;
  for (int i = 1; i <= n; a[i].c = i, i++)
    ;
  mergeS(a, 1, n + 1, 'a');
  for (int i = 1; i <= n; a[i].b = i, i++)
    ;
  mergeS(a, 1, n + 1, 'c');
  for (int i = 1, m = 100000;;) {
    if (a[i].b != 0) {
      c[j].first++;
      c[j].second += a[i].a;
      if (a[i].a < m) m = a[i].a;
      int l = a[i].b;
      a[i].b = 0;
      i = l;
    } else {
      if (c[j].first == 1) {
        c[j].second = 0;
      } else if (c[j].first >= 3) {
        c[j].second += m * (c[j].first - 2);
      }
      m = 100000;
      j++;
      int s = 0;
      for (int k = 1; k <= n; k++) {
        s += a[k].b;
        if (a[k].b != 0) i = k;
      }
      if (s == 0) break;
    }
  }
  long long s = 0;
  for (int i = 1; i <= j; i++) {
    s += c[i].second;
  }
  cout << s << endl;
  return 0;
}
