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;
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U>& a) {
  out << "[" << a.first << " " << a.second << "]";
  return out;
}
template <class T>
ostream& operator<<(ostream& out, const vector<T>& a) {
  out << "[ ";
  for (auto& it : a) out << it << " ";
  out << "]";
  return out;
}
template <class T>
ostream& operator<<(ostream& out, const set<T>& a) {
  out << "[ ";
  for (auto& it : a) out << it << " ";
  out << "]";
  return out;
}
template <class T>
ostream& operator<<(ostream& out, const multiset<T>& a) {
  out << "[ ";
  for (auto& it : a) out << it << " ";
  out << "]";
  return out;
}
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U>& a) {
  for (auto& it : a) out << it.first << " -> " << it.second << " | ";
  return out;
}
template <class T, class U>
ostream& operator<<(ostream& out, const multimap<T, U>& a) {
  for (auto& it : a) out << it.first << " -> " << it.second << " | ";
  return out;
}
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long tree[(1 << 19) + 1];
long long tree2[(1 << 19) + 1];
long long tree3[(1 << 19) + 1];
const long long N = (1 << 19);
void st(long long x, long long v) {
  while (x <= N) {
    tree[x] += v;
    x += (x & -x);
  }
}
long long get(long long x) {
  long long res = 0;
  while (x) {
    res += tree[x];
    x -= (x & -x);
  }
  return res;
}
void st2(long long x, long long v) {
  while (x <= N) {
    tree2[x] += v;
    x += (x & -x);
  }
}
long long get2(long long x) {
  long long res = 0;
  while (x) {
    res += tree2[x];
    x -= (x & -x);
  }
  return res;
}
void st3(long long x, long long v) {
  while (x <= N) {
    tree3[x] += v;
    x += (x & -x);
  }
}
long long get3(long long x) {
  long long res = 0;
  while (x) {
    res += tree3[x];
    x -= (x & -x);
  }
  return res;
}
long long n, a[N], pos[N];
void Main() {
  cin >> n;
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
    pos[a[i]] = i;
  }
  double ans = 0.0;
  for (long long i = 1; i <= n; i++) {
    double pLie = get(pos[i]) * 1.0 * (n - pos[i] + 1);
    pLie /= (n * (n + 1.0) / 2.0);
    ans += pLie / 2.0;
    pLie = (get2(n + 5) - get2(pos[i])) * 1.0 * pos[i];
    pLie /= (n * (n + 1.0)) / 2.0;
    ans += (1.0 * (get3(n + 5) - get3(pos[i])) - pLie) + pLie / 2.0;
    st(pos[i], pos[i]);
    st2(pos[i], n - pos[i] + 1);
    st3(pos[i], 1);
  }
  cout << setprecision(15) << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  Main();
}