Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Inversions After Shuffle

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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:

- Pick a random segment (continuous subsequence) from
*l*to*r*. All segments are equiprobable. - 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. - 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 + p1},*a*_{l - 1 + p2}, ...,*a*_{l - 1 + pk - 1},*a*_{l - 1 + pk},*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 .

Example

Input

3

2 3 1

Output

1.916666666666666666666666666667

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 00:32:25 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|