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 node {
  long prev;
  long next;
  int val;
};
queue<int> merge(queue<int> q1, queue<int> q2) {
  queue<int> ma;
  while (q1.size() || q2.size()) {
    if (!q2.size() || (q1.size() && q1.front() < q2.front())) {
      ma.push(q1.front());
      q1.pop();
    } else {
      ma.push(q2.front());
      q2.pop();
    }
  }
  return ma;
}
queue<int> sort(queue<int> q) {
  queue<int> nq;
  while (q.size() - nq.size() > 1) {
    nq.push(q.front());
    q.pop();
  }
  if (!nq.size()) return q;
  return merge(sort(nq), sort(q));
}
int main() {
  int n;
  cin >> n;
  int wholeMin = INT_MAX;
  int v[n];
  queue<int> q;
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    q.push(v[i]);
    wholeMin = min(wholeMin, v[i]);
  }
  queue<node> nodes;
  q = sort(q);
  while (q.size()) {
    for (int i = 0; i < n; i++) {
      if (q.front() == v[i]) {
        node no;
        no.prev = i;
        no.next = n - q.size();
        no.val = v[i];
        nodes.push(no);
        break;
      }
    }
    q.pop();
  }
  vector<vector<node>> groups;
  vector<node> sub;
  while (nodes.size()) {
    sub.clear();
    node topNode = nodes.front();
    nodes.pop();
    sub.push_back(topNode);
    node curNode = topNode;
    while (curNode.prev != curNode.next) {
      if (curNode.next == nodes.front().prev) {
        curNode = nodes.front();
        nodes.pop();
        sub.push_back(curNode);
        if (curNode.next == topNode.prev) break;
      } else {
        nodes.push(nodes.front());
        nodes.pop();
      }
    }
    groups.push_back(sub);
  }
  long cost = 0;
  for (int i = 0; i < groups.size(); i++) {
    if (groups[i].size() == 1)
      continue;
    else if (groups[i].size() == 2)
      cost += groups[i][0].val + groups[i][1].val;
    else {
      int min = INT_MAX;
      long total = 0;
      for (int k = 0; k < groups[i].size(); k++) {
        min = min < groups[i][k].val ? min : groups[i][k].val;
        total += groups[i][k].val;
      }
      long costInternal = total + min * (groups[i].size() - 2);
      long costExternal =
          total + wholeMin * (groups[i].size() - 2) + (min + wholeMin) * 2;
      cost += costInternal > costExternal ? costExternal : costInternal;
    }
  }
  cout << cost << endl;
  return 0;
}
