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>
#define FOR(i, a, b) for (int i = (a), i##_max = (b); i < i##_max; ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()

using namespace std;
using vi = vector<int>;
using i64 = int64_t;

constexpr int INF = 1 << 30;
constexpr int MOD = 1000000007;

template <typename T>
void print(vector<T> v) {
  REP(i, v.size()) {
    if (i) cout << " ";
    cout << v[i];
  }
  cout << endl;
}

int solve(vi &A, int s) {
  int ans{0};
  vector<bool> V(A.size(), false);
  vi T(10001);
  auto B = A;
  sort(ALL(B));
  REP(i, A.size()) T[B[i]] = i;
  REP(i, A.size()) {
    if (V[i]) continue;
    int cur{i};
    int num{0}, sum{0}, min_{INF};
    while (!V[cur]) {
      V[cur] = true;
      auto w = A[cur];
      ++num;
      sum += w;
      min_ = min(min_, w);
      cur = T[w];
    }
    ans += min(sum + (num - 2) * min_, min_ + sum + (num + 1) * s);
  }
  return ans;
}

int main() {
  int n, s{INF};
  cin >> n;
  vi A(n);
  REP(i, n) {
    cin >> A[i];
    s = min(s, A[i]);
  }
  cout << solve(A, s) << endl;
}
