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;
struct QuickFind {
  vector<long long> r, p;
  vector<vector<long long> > v;
  QuickFind() {}
  QuickFind(long long size) { init(size); }
  void init(long long size) {
    r.resize(size, 0);
    p.resize(size, 0);
    v.resize(size);
    for (long long i = 0; i < size; i++) {
      r[i] = 1, p[i] = i;
      v[i].resize(1, i);
    }
  }
  bool same(long long x, long long y) { return p[x] == p[y]; }
  void unite(long long x, long long y) {
    x = p[x];
    y = p[y];
    if (x == y) return;
    if (r[x] < r[y]) swap(x, y);
    r[x] += r[y];
    for (long long i = 0; i < (long long)v[y].size(); i++) {
      p[v[y][i]] = x;
      v[x].push_back(v[y][i]);
    }
    v[y].clear();
  }
};
signed main() {
  long long n;
  cin >> n;
  vector<long long> a(n);
  for (long long i = 0; i < n; i++) cin >> a[i];
  vector<long long> b(a);
  sort(b.begin(), b.end());
  map<long long, long long> p, q;
  for (long long i = 0; i < n; i++) {
    p[a[i]] = i;
    q[b[i]] = i;
  }
  QuickFind qf(n);
  for (long long i = 0; i < n; i++) qf.unite(i, p[b[i]]);
  long long ans = 0;
  for (long long i = 0; i < n; i++) {
    long long k = qf.v[i].size();
    if (qf.p[i] != i || k == 1) continue;
    long long m = a[qf.v[i][0]];
    long long tmp = 0;
    for (long long j = 0; j < k; j++) {
      tmp += a[qf.v[i][j]];
      m = min(m, a[qf.v[i][j]]);
    }
    ans += min(tmp + m * (k - 2), tmp + (m + b[0]) * 2 + b[0] * (k - 2));
  }
  cout << ans << endl;
  return 0;
}
