Problem: You are given a permutation of integers from 1 to n. Exactly once you apply the following operation to this permutation: pick a random segment and shuffle its elements. Formally:

  1. Pick a random segment (continuous subsequence) from l to r. All <image> segments are equiprobable. 
  2. Let k = r - l + 1, i.e. the length of the chosen segment. Pick a random permutation of integers from 1 to k, p1, p2, ..., pk. All k! permutation are equiprobable. 
  3. This permutation is applied to elements of the chosen segment, i.e. permutation a1, a2, ..., al - 1, al, al + 1, ..., ar - 1, ar, ar + 1, ..., an is transformed to a1, a2, ..., al - 1, al - 1 + p1, al - 1 + p2, ..., al - 1 + pk - 1, al - 1 + pk, ar + 1, ..., an. 



Inversion if a pair of elements (not necessary neighbouring) with the wrong relative order. In other words, the number of inversion is equal to the number of pairs (i, j) such that i < j and ai > aj. Find the expected number of inversions after we apply exactly one operation mentioned above.

Input

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the length of the permutation.

The second line contains n distinct integers from 1 to n — elements of the permutation.

Output

Print one real value — the expected number of inversions. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 9. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if <image>.

Example

Input

3
2 3 1


Output

1.916666666666666666666666666667

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
void OUT_TST(string s, istream_iterator<string> it) { cerr << s; }
template <typename T, typename... Args>
void OUT_TST(string s, istream_iterator<string> it, T a, Args... args) {
  cerr << *it << "=" << a << " ";
  OUT_TST(s, ++it, args...);
}
template <class T>
void rd(T& ret) {
  ret = 0;
  bool ok = 0, u = 0;
  for (;;) {
    int c = getchar();
    if (c >= '0' && c <= '9')
      ret = (ret << 3) + (ret << 1) + c - '0', ok = 1;
    else if (c == '-')
      u = 1;
    else if (ok) {
      if (u) ret *= -1;
      return;
    }
  }
}
long long powmod(long long p, long long n, long long mod) {
  long long ret = 1;
  for (; n; n >>= 1) {
    if (n & 1) ret = ret * p % mod;
    p = p * p % mod;
  }
  return ret;
}
template <class T>
bool chmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool chmax(T& a, const T& b) {
  return b > a ? a = b, 1 : 0;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
const int N = (int)1e5 + 9;
struct SegTree {
  int n;
  long long sum[N << 2];
  int count[N << 2];
  void clear(int _n) {
    n = _n;
    memset(sum, 0, sizeof(sum[0]) * n * 4);
    memset(count, 0, sizeof(count[0]) * n * 4);
  }
  void merge(int l, int r, int m, int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    count[rt] = count[rt << 1] + count[rt << 1 | 1];
  }
  void update(int p, long long v, int l, int r, int rt) {
    if (l == p && r == p) {
      sum[rt] = v;
      count[rt] = 1;
      ;
      return;
    }
    int m = (l + r) >> 1;
    if (p <= m)
      update(p, v, l, m, rt << 1);
    else
      update(p, v, m + 1, r, rt << 1 | 1);
    merge(l, r, m, rt);
  }
  pair<int, long long> query(int ql, int qr, int l, int r, int rt) {
    if (ql <= l && r <= qr) {
      return pair<int, long long>(count[rt], sum[rt]);
    }
    int m = (l + r) >> 1;
    long long s = 0;
    int cnt = 0;
    if (ql <= m) {
      auto t = query(ql, qr, l, m, rt << 1);
      cnt += t.first;
      s += t.second;
    }
    if (qr > m) {
      auto t = query(ql, qr, m + 1, r, rt << 1 | 1);
      cnt += t.first;
      s += t.second;
    }
    return {cnt, s};
  }
  void update(int p, long long v) { update(p, v, 0, n - 1, 1); }
  pair<int, long long> query(int ql, int qr) {
    return query(ql, qr, 0, n - 1, 1);
  }
} tree;
int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  cout << std::fixed;
  cout.precision(10);
  int n;
  cin >> n;
  vector<int> an(n);
  tree.clear(n);
  double ans = 0, tmp = (n + 1.0) * n / 2.0;
  for (int i = 0; i < n; ++i) {
    cin >> an[i];
    --an[i];
    auto pr = tree.query(an[i] + 1, n - 1);
    ans += pr.first;
    ans -= pr.second * (n - i + 0.0) / tmp;
    tree.update(an[i], i + 1);
  }
  for (int i = 1; i <= n; ++i) {
    ans += (n - i + 1.0) * i * (i - 1.0) / 2 / 2 / (n * (n + 1.0) / 2.0);
  }
  cout << ans << endl;
  return 0;
}