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 Data {
  Data() : w(0), from(0), to(0), load(0) {}
  int w;
  int from;
  int to;
  int load;
};
struct DataWeightComparator {
  bool operator()(const Data* d1, const Data* d2) { return (d1->w < d2->w); }
};
struct DataLoadComparator {
  bool operator()(const Data* d1, const Data* d2) {
    return (d1->load < d2->load);
  }
};
static Data* GetMinLoadData(Data* d1, Data* d2) {
  if (0 == d1) return d2;
  if (0 == d2) return d1;
  return (d1->load > d2->load ? d2 : d1);
}
struct SegmentTree {
  int base;
  vector<Data*> vS;
  void init(int n) {
    base = 1;
    while (base < n) base *= 2;
    int s = 2 * base - 1;
    vS.reserve(s);
    while (s--) vS.push_back(0);
  }
  void update(int t, Data* d) {
    int r = t + base - 1;
    vS[r] = d;
    while (r > 0) {
      r = (r - 1) / 2;
      vS[r] = GetMinLoadData(vS[2 * r + 1], vS[2 * r + 2]);
    }
  }
  Data* query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l)
      return 0;
    else if (a <= l && r <= b)
      return vS[k];
    else {
      int m = (l + r) / 2;
      Data* lm = query(a, b, 2 * k + 1, l, m);
      Data* mr = query(a, b, 2 * k + 2, m, r);
      return GetMinLoadData(lm, mr);
    }
  }
  Data* query(int a, int b) { return query(a, b + 1, 0, 0, base); }
};
int main() {
  int n;
  cin >> n;
  vector<Data*> vD, vW, vL;
  vD.reserve(n);
  for (int i = 0; i < n; ++i) {
    Data* d = new Data();
    cin >> d->w;
    d->from = i;
    vD.push_back(d);
  }
  vW = vD;
  sort(vW.begin(), vW.end(), DataWeightComparator());
  SegmentTree tree;
  tree.init(n);
  for (int i = 0; i < n; ++i) {
    vW[i]->to = i;
    if (vW[i]->from == vW[i]->to) {
      vW[i]->load = 0;
      tree.update(i, 0);
    } else {
      vW[i]->load = vD[vW[i]->from]->w + vD[vW[i]->to]->w;
      tree.update(i, vW[i]);
    }
  }
  int c = 0, from, to;
  Data* d;
  while ((d = tree.query(0, n - 1)) != 0) {
    to = d->to;
    from = d->from;
    c += d->load;
    swap(vD[to], vD[from]);
    vD[to]->from = to;
    vD[from]->from = from;
    vD[to]->load = 0;
    tree.update(to, 0);
    if (vW[from]->from == vW[from]->to) {
      vD[from]->load = 0;
      tree.update(from, 0);
    } else {
      vD[from]->load = vD[from]->w + vD[vD[from]->to]->w;
      vW[from]->load = vW[from]->w + vD[vW[from]->to]->w;
      tree.update(from, vW[from]);
      tree.update(vD[from]->to, vD[from]);
    }
  }
  cout << c << "\n";
  for (int i = 0; i < n; ++i) delete vD[i];
  return 0;
}
