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;
using ll = long long;
const int N = 1e5;
struct arbol {
  int izq, der, cen;
  arbol *hijoIzq, *hijoDer;
  int cant;
  ll suma;
  arbol(int izq, int der)
      : izq(izq),
        der(der),
        cen((izq + der) / 2),
        hijoIzq(nullptr),
        hijoDer(nullptr),
        cant(0),
        suma(0LL) {}
  void inserta(int x, ll i) {
    cant++;
    suma += i;
    if (izq == der) return;
    if (x <= cen) {
      if (!hijoIzq) hijoIzq = new arbol(izq, cen);
      hijoIzq->inserta(x, i);
    } else {
      if (!hijoDer) hijoDer = new arbol(cen + 1, der);
      hijoDer->inserta(x, i);
    }
  }
  pair<int, ll> consulta(int y) {
    if (y < izq) {
      return pair<int, ll>(cant, suma);
    }
    auto i = (y < cen && hijoIzq) ? hijoIzq->consulta(y) : pair<int, ll>(0, 0);
    auto d = (hijoDer) ? hijoDer->consulta(y) : pair<int, ll>(0, 0);
    return pair<int, ll>(i.first + d.first, i.second + d.second);
  }
};
int main() {
  ll n;
  scanf("%lld", &n);
  double res = 0;
  for (ll k = 2; k <= n; k++) {
    res += (n - k + 1) * k * (k - 1);
  }
  res /= 4;
  arbol A(1, n + 1);
  for (int i = 1; i <= n; i++) {
    int ai;
    scanf("%d", &ai);
    auto p = A.consulta(ai);
    res += p.first * (n * (n + 1) / 2) - (n - i + 1) * p.second;
    A.inserta(ai, i);
  }
  res = 2 * res / (n * (n + 1));
  printf("%.20lf\n", res);
}