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 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*$, $*p*_{1}, *p*_{2}, ..., *p*_{*k*}$. All $*k*!$ permutation are equiprobable.
3. This permutation is applied to elements of the chosen segment, i.e. permutation $*a*_{1}, *a*_{2}, ..., *a*_{*l* - 1}, *a*_{*l*}, *a*_{*l* + 1}, ..., *a*_{*r* - 1}, *a*_{*r*}, *a*_{*r* + 1}, ..., *a*_{*n*}$ is transformed to $*a*_{1}, *a*_{2}, ..., *a*_{*l* - 1}, *a*_{*l* - 1 + *p*_{1}}, *a*_{*l* - 1 + *p*_{2}}, ..., *a*_{*l* - 1 + *p*_{*k* - 1}}, *a*_{*l* - 1 + *p*_{*k*}}, *a*_{*r* + 1}, ..., *a*_{*n*}$.

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 $*a*_{*i*} > *a*_{*j*}$. 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 .