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 val {
  int n;
  size_t i;
  size_t rank;
};
bool operator<(val v1, val v2) { return v1.n < v2.n; }
val make_val(int n, size_t i) {
  val v;
  v.n = n;
  v.i = i;
  return v;
}
vector<val> ns;
map<vector<val>, int> costs;
int min_cost(vector<val>);
int main() {
  size_t n;
  cin >> n;
  int v;
  for (size_t i = 0; i < n; ++i) {
    cin >> v;
    ns.push_back(make_val(v, i));
  }
  vector<val> ns_uns = ns;
  sort(ns.begin(), ns.end());
  costs[ns] = 0;
  for (size_t i = 0; i < n; ++i) {
    ns_uns[ns[i].i].rank = i;
  }
  int cost = 0;
  for (size_t i = 0; i < n; ++i) {
    size_t r = ns_uns[i].rank;
    if (r != i and ns_uns[r].rank == i) {
      cost += ns_uns[i].n + ns_uns[r].n;
      swap(ns_uns[i], ns_uns[r]);
    }
  }
  cost += min_cost(ns_uns);
  cout << cost << endl;
}
int min_cost(vector<val> vv) {
  if (costs.count(vv)) {
    return costs[vv];
  }
  map<size_t, int> costs_by_swap_choice;
  for (size_t i = 0; i < vv.size(); ++i) {
    size_t i_rank = vv[i].rank;
    if (i_rank != i) {
      swap(vv[i], vv[i_rank]);
      costs_by_swap_choice[i] = vv[i].n + vv[i_rank].n + min_cost(vv);
      swap(vv[i], vv[i_rank]);
    }
  }
  int min_cost = numeric_limits<int>::max();
  for (auto entry : costs_by_swap_choice) {
    min_cost = min(entry.second, min_cost);
  }
  costs[vv] = min_cost;
  return min_cost;
}
