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.util.Scanner;

public class ProblemE {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);

		//Step 0: IO
		int n = input.nextInt();
		int[] arr = new int[n];
		for (int a = 0; a < n; a++) {
			arr[a] = input.nextInt();
		}
		
		
		//Step 1: Get the total inversions of the sequence
		long totalInversions = 0;
		SumSegmentTree bigInvert = new SumSegmentTree(0, n);
		for(int a = 0; a < n; a++){
			totalInversions += arr[a]-bigInvert.query(0, arr[a]-1)-1;
			bigInvert.insert(arr[a], 1);
		}
//		System.out.println(totalInversions);
		
		
		//Step 2: Get the average number of inversions in a random sequence of random size
		double total = 0;
		for(long sz = 1; sz <= n; sz++){
			total += (n-sz+1.0)*(sz)*(sz-1)/4.0;
		}
		long nLong = n;
		total = total/((nLong * (nLong+1))/2);
//		System.out.println("Expected value of random sequence: " + total);
		
		//Step 3: Get the number of inversions in the expected sequence
		SumSegmentTree bigTree = new SumSegmentTree(0, n);
		double expectedInversionsInSequence = 0.0;
		for(int a = 0; a < n; a++){
			int val = arr[a];
			long multiply = bigTree.query(arr[a], n) * (nLong-a);
			expectedInversionsInSequence += multiply;
			bigTree.insert(arr[a], a+1);
		}
		expectedInversionsInSequence = expectedInversionsInSequence/((nLong * (nLong+1))/2);
//		System.out.println(expectedInversionsInSequence);
		System.out.println(totalInversions-expectedInversionsInSequence+total);
	}

	public static class SumSegmentTree {
		int leftRange;
		int rightRange;
		long value;
		SumSegmentTree left;
		SumSegmentTree right;

		public SumSegmentTree(int _left, int _right) {
			leftRange = _left;
			rightRange = _right;
			if (_left != _right) {
				left = new SumSegmentTree(_left, (_left + _right) / 2);
				right = new SumSegmentTree((_left + _right) / 2 + 1, _right);
			}
			value = 0;
		}

		public void insert(int id, long _value) {
			if (id <= rightRange && id >= leftRange) {
				value += _value;
				if (leftRange != rightRange) {
					left.insert(id, _value);
					right.insert(id, _value);
				}
			}
		}

		public long query(int _left, int _right) {
			if (_left > rightRange || _right < leftRange) {
				return 0;
			}
			if (_left <= leftRange && _right >= rightRange) {
				return value;
			}
			return left.query(_left, _right) + right.query(_left, _right);
		}

		public String toString() {
			return "(" + leftRange + ", " + rightRange + "): " + value + "\n" + ((left == null) ? "" : left)
					+ ((right == null) ? "" : right);
		}
	}
}