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

Solution:


# Python3 program to count inversions using  
# Binary Indexed Tree  
  
# Returns sum of arr[0..index]. This function 
# assumes that the array is preprocessed and  
# partial sums of array elements are stored  
# in BITree[].  
def getSum( BITree, index): 
    sum = 0 # Initialize result  
      
    # Traverse ancestors of BITree[index]  
    while (index > 0):  
  
        # Add current element of BITree to sum  
        sum += BITree[index]  
  
        # Move index to parent node in getSum View  
        index -= index & (-index)  
  
    return sum
  
# Updates a node in Binary Index Tree (BITree)  
# at given index in BITree. The given value 
# 'val' is added to BITree[i] and all of its 
# ancestors in tree.  
def updateBIT(BITree, n, index, val): 
  
    # Traverse all ancestors and add 'val'  
    while (index <= n):  
  
        # Add 'val' to current node of BI Tree  
        BITree[index] += val  
  
        # Update index to that of parent 
        # in update View  
        index += index & (-index)  
  
# Returns count of inversions of size three  
def getInvCount(arr, n): 
  
    invcount = 0 # Initialize result  
  
    # Find maximum element in arrays  
    maxElement = max(arr) 
  
    # Create a BIT with size equal to  
    # maxElement+1 (Extra one is used  
    # so that elements can be directly  
    # be used as index) 
    BIT = [0] * (maxElement + 1)  
    for i in range(1, maxElement + 1):  
        BIT[i] = 0
    for i in range(n - 1, -1, -1): 
        invcount += getSum(BIT, arr[i] - 1)  
        updateBIT(BIT, maxElement, arr[i], 1)  
    return invcount  

def getInvCountAdv(arr, n): 
  
    invcount = 0 # Initialize result  
  
    # Find maximum element in arrays  
    maxElement = max(arr) 
  
    # Create a BIT with size equal to  
    # maxElement+1 (Extra one is used  
    # so that elements can be directly  
    # be used as index) 
    BIT = [0] * (maxElement + 1)  
    for i in range(1, maxElement + 1):  
        BIT[i] = 0
    for i in range(n - 1, -1, -1): 
        invcount += (i + 1) * getSum(BIT, arr[i] - 1)  
        updateBIT(BIT, maxElement, arr[i], n-i)  
    return invcount  
      
# Driver code  
n = int(input())
a = list(map(int,input().split())) 
InvCount = getInvCount(a, n)
InvCountAdv = getInvCountAdv(a,n)
thirdSum = 0
for i in range(1,n+1):
    thirdSum += i * (i - 1) * (n- i + 1) / 2
print(InvCount - InvCountAdv / (n * (n + 1)) * 2 + thirdSum / (n * (n + 1)))
      
# This code is contributed by 
# Shubham Singh(SHUBHAMSINGH10)