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;
const int maxn = 1e3 + 5;
long long a[maxn], p[maxn], n;
vector<int> v;
long long sum = 0;
void solve() {
  vector<int>::iterator it = v.begin();
  int t = *it;
  v.erase(v.begin());
  if (!v.empty()) it = v.begin();
  while (!v.empty()) {
    int f = 0;
    int b = *it;
    if (b == p[t]) {
      if (t == p[b]) f = 1;
      swap(a[p[t]], a[p[b]]);
      sum += t + *it + 2;
      v.erase(it);
      if (f == 1 && !v.empty()) t = v[0], v.erase(v.begin());
      if (!v.empty()) it = v.begin();
    } else {
      it++;
      if (it == v.end()) it = v.begin();
    }
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    --a[i];
    p[a[i]] = i;
    if (a[i] != i) v.push_back(a[i]);
  }
  sort(v.begin(), v.end());
  solve();
  printf("%d\n", sum);
  return 0;
}
