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 = int;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;
constexpr long long INF = numeric_limits<LL>::max();
const double PI = acos(-1);
struct Tll {
  LL first, second, third;
};
struct Fll {
  LL first, second, third, fourd;
};
LL h, w, n, m, k, t, s, q, last, cnt, sum, ans, dp[10000], a[2000000],
    b[2000000];
string str, ss;
bool f[1100][1100];
char c;
int di[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
struct Edge {
  LL to, cost;
};
vector<Edge> vec[200000];
vector<LL> v, pick[200000];
map<string, vector<LL>> ma;
multiset<LL> st[3];
void YN(bool f) {
  if (f)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}
void yn(bool f) {
  if (f)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}
vector<int> kosaraju() {
  int sz = 0;
  vector<Edge> rg[50000];
  vector<int> stk, cmp(n, -1), added(n), visited(n), ord(n);
  for (LL i = 0; i < n; i++) {
    sz += vec[i].size();
    for (const Edge &e : vec[i]) rg[e.to].push_back(Edge{(int)i, e.cost});
  }
  stk.resize(n + sz);
  sz = 0;
  for (int i = 0; i < n; i++) {
    if (visited[i]) continue;
    int s = 0;
    stk[s++] = i;
    while (s != 0) {
      int v = stk[s - 1];
      visited[v] = true;
      bool pushed = false;
      for (auto &e : vec[v]) {
        int dst = e.to;
        if (!visited[dst]) {
          stk[s++] = dst;
          pushed = true;
        }
      }
      if (pushed) continue;
      int t = stk[s - 1];
      if (!added[t]) {
        added[t] = true;
        ord[n - ++sz] = t;
      }
      --s;
    }
  }
  int k = 0;
  for (int &u : ord) {
    if (cmp[u] != -1) continue;
    int s = 0;
    stk[s++] = u;
    while (s != 0) {
      int v = stk[--s];
      cmp[v] = k;
      for (auto &e : rg[v]) {
        int d = e.to;
        if (cmp[d] == -1) stk[s++] = d;
      }
    }
    ++k;
  }
  return cmp;
}
map<int, int> zip;
int unzip[200000];
int compress(vector<int> &x) {
  sort(x.begin(), x.end());
  x.erase(unique(x.begin(), x.end()), x.end());
  for (int i = 0; i < x.size(); i++) {
    zip[x[i]] = i;
    unzip[i] = x[i];
  }
  return x.size();
}
int main() {
  cin >> n;
  for (LL i = 0; i < n; i++) {
    cin >> a[i];
    v.push_back(a[i]);
  }
  compress(v);
  v.clear();
  for (LL i = 0; i < n; i++) {
    vec[i].push_back(Edge{zip[a[i]], 1});
  }
  v = kosaraju();
  for (LL i = 0; i < v.size(); i++) {
    pick[v[i]].push_back(i);
  }
  for (LL i = 0; i < n; i++) {
    sum = 0;
    LL mn = INF;
    if (pick[i].size() > 1) {
      for (LL j = 0; j < pick[i].size(); j++) {
        sum += unzip[pick[i][j]];
        mn = min(mn, pick[i][j]);
      }
      ans += min(sum + unzip[mn] * (pick[i].size() - 2),
                 sum + unzip[0] * (pick[i].size()) + unzip[mn]);
    }
  }
  cout << ans << endl;
  return 0;
}
