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;
using ll = long long;
struct Value {
  ll v;
  ll idx;
};
class lesserValue {
 public:
  bool operator()(const Value &x, const Value &y) { return x.v < y.v; }
};
void print(const vector<Value> &x) {
  for (ll i = 0; i < x.size(); ++i) {
    if (i != 0) cout << " ";
    cout << x[i].v << "," << x[i].idx;
  }
  cout << endl;
}
int main() {
  ll n;
  cin >> n;
  vector<Value> w(n);
  for (ll i = 0; i < n; ++i) {
    scanf("%lld", &w[i].v);
    w[i].idx = i;
  }
  vector<Value> orig(w);
  sort(w.begin(), w.end(), lesserValue());
  unordered_set<ll> memo;
  ll ans = 0;
  for (ll i = 0; i < n; ++i) {
    if (memo.end() != memo.find(i)) {
      continue;
    }
    memo.insert(i);
    vector<ll> t;
    ll j = i;
    do {
      t.push_back(orig[j].v + w[j].v);
      memo.insert(j);
      j = w[j].idx;
    } while (i != j);
    ans += accumulate(t.begin(), t.end(), 0);
    if (t.size() > 0) {
      ans -= *max_element(t.begin(), t.end());
    }
  }
  cout << ans << endl;
  return 0;
}
