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;
template <typename T>
T &chmin(T &a, const T &b) {
  return a = min(a, b);
}
template <typename T>
T &chmax(T &a, const T &b) {
  return a = max(a, b);
}
using ll = long long;
using ld = long double;
const int INF = 1e9;
const ld eps = 1e-9, pi = acos(-1.0);
struct UnionFind {
  vector<int> parent;
  UnionFind(int N) : parent(N, -1){};
  int root(int n) { return parent[n] < 0 ? n : parent[n] = root(parent[n]); }
  bool merge(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (parent[x] > parent[y]) swap(x, y);
    if (parent[x] == parent[y]) parent[x]--;
    parent[y] = x;
    return true;
  }
  bool judge(int a, int b) { return root(a) == root(b); }
};
int binarySearch(int *target, int num, int l, int r) {
  if (l == r) return l;
  int pivot = (l + r) / 2;
  if (*(target + pivot) == num) return pivot;
  return *(target + pivot) > num ? binarySearch(target, num, l, pivot)
                                 : binarySearch(target, num, pivot + 1, r);
}
int main() {
  int n;
  cin >> n;
  int a[n], org[n];
  int res = 0;
  UnionFind grp = UnionFind(n);
  for (int i = 0; i < (int)(n); i++) {
    cin >> a[i];
    org[i] = a[i];
  }
  sort(a, a + n);
  for (int i = 0; i < (int)(n); i++) {
    int place = binarySearch(a, org[i], 0, n - 1);
    grp.merge(i, place);
  }
  for (int i = 0; i < (int)(n); i++) {
    if (grp.parent[i] == -1) continue;
    if (grp.parent[i] < 0) {
      vector<int> target;
      for (int j = 0; j < (int)(n); j++)
        if (grp.judge(i, j)) target.push_back(a[j]);
      sort(target.begin(), target.end());
      res += accumulate(target.begin(), target.end(),
                        target[0] * (target.size() - 2));
    }
  }
  cout << res << endl;
  return 0;
}
