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;
vector<string> split(const string &s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
void err(vector<string>::iterator it) {}
template <typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
  cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << '\n';
  err(++it, args...);
}
const long long NMAX = 100005;
long long n, a[NMAX], AIB[NMAX], AIBM[NMAX];
long long dp[NMAX], sum[NMAX], sum1[NMAX];
long long zeros(long long x) { return x ^ (x & (x - 1)); }
void Update(long long poz, long long val, long long *A) {
  for (long long i = poz; i < NMAX; i += zeros(i)) A[i] += val;
}
long long Query(long long poz, long long *A) {
  long long i, rez = 0;
  for (i = poz; i >= 1; i -= zeros(i)) rez += A[i];
  return rez;
}
long long Gauss(long long x) { return x * (x + 1) / 2; }
long long GaussPat(long long x) { return x * (x + 1) * (2 * x + 1) / 6; }
int32_t main() {
  long long i;
  cin.sync_with_stdio(false);
  cin >> n;
  for (i = 1; i <= n; i++) {
    cin >> a[i];
    dp[i] = Query(NMAX - 1, AIB) - Query(a[i], AIB);
    sum[i] = sum[i - 1] + dp[i];
    sum1[i] = sum1[i - 1] + sum[i];
    Update(a[i], 1, AIB);
  }
  double sol = 0;
  for (i = 1; i <= n; i++) {
    sol += (n - i + 1) * (sum[i - 1] + sum[n]);
    sol -= sum1[n] - sum1[i - 1];
    sol += (GaussPat(n - i + 1) - Gauss(n - i + 1)) / 4.0;
  }
  for (i = 1; i <= n; i++) {
    sol += i * (n - i + 1) * dp[i] -
           (n - i + 1) * (Query(NMAX - 1, AIBM) - Query(a[i], AIBM));
    Update(a[i], i, AIBM);
  }
  sol = sol / (1.0 * (n * (n + 1) / 2));
  cout << setprecision(10) << fixed;
  cout << sol << "\n";
  return 0;
}