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 JAVA):

Solution:
import java.io.*;
import java.util.*;

public class inversion_shuffle {

	static int p[]= new int[100_001];
	
	static class F {
		long[] t;
		public F(int n) {
			t=new long[n];
		}
		long get(int r) {
			long res = 0;
			for (int i = r; i >= 0; i &= i + 1, --i) {
				res += t[i];
			}
			return res;
		}
		long get(int l, int r) {
			return get(r) - get(l - 1);
		}
		void update(int pos, long val) {
			for (int i = pos; i < t.length; i |= i + 1) {
				t[i] += val;
			}
		}
	};
	
	public static void main(String[] args) throws FileNotFoundException {
		InputStream is = System.in;

		Scanner sc = new Scanner(new InputStreamReader(is));
		int N=sc.nextInt();
		for (int i=0; i<N; i++) p[i] = sc.nextInt()-1;
		F f1=new F(N);
		F f2=new F(N);
		double tb=0;
		for (int i=0; i<N; i++) {
			tb += f1.get(0, N - 1) * 1.0 * (N - i) / N / (N + 1);
			tb += f2.get(p[i] + 1, N - 1);
			tb -= f1.get(p[i] + 1, N - 1) * 1.0 * (N - i) / N / (N + 1) * 2;
 
			f2.update(p[i], +1);
			f1.update(p[i], i + 1);
			
		}
		System.out.println(tb);
	}
}