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:  Pick a random segment (continuous subsequence) from l to r. All $\frac{n(n + 1)}{2}$ 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 + 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 $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-9}$.


-----Example-----
Input
3
2 3 1

Output
1.916666666666666666666666666667

Difficulty: interview

Starter code:

Solutions:


# 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) 




# 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) 




# 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)))
      
# Some part of this code is contributed by 
# Shubham Singh(SHUBHAMSINGH10)