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>
#pragma warning(disable : 4996)
using namespace std;
const int My_Inf = 2147483647;
const long long int My_LInf = 9223372036854775807;
int dat[2 * (1 << 18)];
struct segtree {
  int N;
  segtree() {}
  segtree(int n) {
    N = 1;
    while (N < n) N *= 2;
    for (int i = 0; i < 2 * N - 1; i++) dat[i] = My_Inf;
  }
  void update(int k, int n) {
    k += N - 1;
    dat[k] = n;
    while (k > 0) {
      k = (k - 1) / 2;
      int al(dat[k * 2 + 1]);
      int ar(dat[k * 2 + 2]);
      dat[k] = min(al, ar);
    }
  }
  int query(int a, int b) { return query(a, b, 0, 0, N); }
  int query(int a, int b, int k, int l, int r) {
    if (r <= a or b <= l) return My_Inf;
    if (a <= l and r <= b) return dat[k];
    int m = (l + r) / 2;
    int al(query(a, b, k * 2 + 1, l, m));
    int ar(query(a, b, k * 2 + 2, m, r));
    return min(al, ar);
  }
};
struct bag {
  int place;
  int goodplace;
  int weight;
};
int main() {
  int n;
  cin >> n;
  vector<bag> bags;
  vector<int> heavys;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    bags.push_back(bag{i, 0, a});
    heavys.push_back(a);
  }
  sort(bags.begin(), bags.end(),
       [](const bag& l, const bag& r) { return l.weight < r.weight; });
  for (int i = 0; i < bags.size(); ++i) {
    bags[i].goodplace = i;
  }
  segtree seg(n);
  for (int i = 0; i < n; ++i) {
    if (bags[i].place != bags[i].goodplace) {
      seg.update(i, i);
    }
  }
  long long int ans = 0;
  while (1) {
    int a = seg.query(0, n);
    if (a == My_Inf) {
      break;
    } else {
      for (int i = 0; i < n; ++i) {
        if (bags[a].place == i) {
          ans += bags[i].weight + bags[a].weight;
          swap(bags[a].place, bags[i].place);
          seg.update(i, My_Inf);
          if (bags[a].place == bags[a].goodplace) {
            seg.update(a, My_Inf);
          }
          break;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}
