You are given a permutation of n numbers p_1, p_2, ..., p_{n}. We perform k operations of the following type: choose uniformly at random two indices l and r (l ≤ r) and reverse the order of the elements p_{l}, p_{l} + 1, ..., p_{r}. Your task is to find the expected value of the number of inversions in the resulting permutation.


-----Input-----

The first line of input contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10^9). The next line contains n integers p_1, p_2, ..., p_{n} — the given permutation. All p_{i} are different and in range from 1 to n.

The problem consists of three subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

  In subproblem G1 (3 points), the constraints 1 ≤ n ≤ 6, 1 ≤ k ≤ 4 will hold.  In subproblem G2 (5 points), the constraints 1 ≤ n ≤ 30, 1 ≤ k ≤ 200 will hold.  In subproblem G3 (16 points), the constraints 1 ≤ n ≤ 100, 1 ≤ k ≤ 10^9 will hold. 


-----Output-----

Output the answer with absolute or relative error no more than 1e - 9.


-----Examples-----
Input
3 1
1 2 3

Output
0.833333333333333

Input
3 4
1 3 2

Output
1.458333333333334



-----Note-----

Consider the first sample test. We will randomly pick an interval of the permutation (1, 2, 3) (which has no inversions) and reverse the order of its elements. With probability $\frac{1}{2}$, the interval will consist of a single element and the permutation will not be altered. With probability $\frac{1}{6}$ we will inverse the first two elements' order and obtain the permutation (2, 1, 3) which has one inversion. With the same probability we might pick the interval consisting of the last two elements which will lead to the permutation (1, 3, 2) with one inversion. Finally, with probability $\frac{1}{6}$ the randomly picked interval will contain all elements, leading to the permutation (3, 2, 1) with 3 inversions. Hence, the expected number of inversions is equal to $\frac{1}{2} \cdot 0 + \frac{1}{6} \cdot 1 + \frac{1}{6} \cdot 1 + \frac{1}{6} \cdot 3 = \frac{5}{6}$.

Difficulty: interview

Starter code:

Solutions:
from sys import stdin, stdout
from math import *
from itertools import *
from copy import *

s = 0
invs = 0

def calc_invertions(a):
    s = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            s += 1 if a[i] > a[j] else 0
    return s

def do_flips(arr, num):
    nonlocal s, invs
    if num == 0:
        invs += 1
        s += calc_invertions(arr)
    else:
        for i in range(len(arr)):
            for j in range(i, len(arr)):
                for k in range((j - i + 1) // 2):
                    arr[i + k], arr[j - k] = arr[j - k], arr[i + k]
                do_flips(arr, num - 1)
                for k in range((j - i + 1) // 2):
                    arr[i + k], arr[j - k] = arr[j - k], arr[i + k]
    
def solve(test):
    ints = list(map(int, test.strip().split()))
    n, m = ints[:2]
    arr = ints[2:]
    do_flips(arr, m)
    return s / invs

stdout.write(str(solve(stdin.read())))


def main():
    def rec(k):
        nonlocal S, N
        if k == 0:
            for l in range(n):
                for r in range(l + 1, n):
                    if per[l] > per[r]:
                        S += 1
            N += 1
            return
        for l in range(n):
            for r in range(l + 1, n + 1):
                per[l: r] = reversed(per[l: r])
                rec(k - 1)
                per[l: r] = reversed(per[l: r])
    
    n, k = [int(i) for i in input().split()]
    per = [int(i) for i in input().split()]
    
    S = N = 0
    rec(k)
    print(S / N)
    

main()


import operator
import itertools


def count_inversions(ns):

    return sum(itertools.starmap(operator.gt, itertools.combinations(ns, 2)))


def rotate(ns, l, r):

    return ns[:l] + ns[l:r + 1][::-1] + ns[r + 1:]


def rotate_times(ns, k):

    if k == 0:

        yield ns

    else:

        for l, r in itertools.combinations_with_replacement(list(range(len(ns))), 2):

            yield from rotate_times(rotate(ns, l, r), k - 1)


n, k = list(map(int, str.split(input())))
ns = tuple(map(int, str.split(input())))
inv = tuple(map(count_inversions, rotate_times(ns, k)))
print(sum(inv) / len(inv))


def genrevs(n):
    ans = []
    for l in range(n):
        for r in range(l, n):
            ans.append((l, r))
    return ans

def cnt_rev(p):
    n = len(p)
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            if p[i] > p[j]:
                ans += 1
    return ans

def repl(l, r):
    nonlocal p
    for c in range((r - l + 1) // 2):
        p[l + c], p[r - c] = p[r - c], p[l + c]


n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
rev = genrevs(n)
lr = len(rev)
tr = []
ans = 0
if k == 1:
    for i in range(lr):
        repl(rev[i][0], rev[i][1])
        ans += cnt_rev(p)
        repl(rev[i][0], rev[i][1])
    print(ans / lr)

if k == 2:
    for k1 in range(lr):
        repl(rev[k1][0], rev[k1][1])
        for k2 in range(lr):
            repl(rev[k2][0], rev[k2][1])
            ans += cnt_rev(p)
            repl(rev[k2][0], rev[k2][1])
        repl(rev[k1][0], rev[k1][1])
    print(ans / (lr ** 2))

if k == 3:
    for k1 in range(lr):
        repl(rev[k1][0], rev[k1][1])
        for k2 in range(lr):
            repl(rev[k2][0], rev[k2][1])
            for k3 in range(lr):
                repl(rev[k3][0], rev[k3][1])
                ans += cnt_rev(p)
                repl(rev[k3][0], rev[k3][1])
            repl(rev[k2][0], rev[k2][1])
        repl(rev[k1][0], rev[k1][1])
    print(ans / (lr ** 3))

if k == 4:
    for k1 in range(lr):
        repl(rev[k1][0], rev[k1][1])
        for k2 in range(lr):
            repl(rev[k2][0], rev[k2][1])
            for k3 in range(lr):
                repl(rev[k3][0], rev[k3][1])
                for k4 in range(lr):
                    repl(rev[k4][0], rev[k4][1])
                    ans += cnt_rev(p)
                    repl(rev[k4][0], rev[k4][1])
                repl(rev[k3][0], rev[k3][1])
            repl(rev[k2][0], rev[k2][1])
        repl(rev[k1][0], rev[k1][1])
    print(ans / (lr ** 4))


n, k = [int(x) for x in input().split()]
base = [int(x) for x in input().split()]


def invert_count(l):
    swaps = 0
    for i in range(len(l)):
        while i > 0 and l[i-1] > l[i]:
            temp = l[i-1]
            l[i-1] = l[i]
            l[i] = temp
            swaps += 1
            i -= 1
    return swaps


def make_reflects(base,rem=k):
    if rem == 0:
        return invert_count(base)
    else:
        ans = 0
        for i in range(len(base)):
            for j in range(i+1,len(base)):
                new = base[:i] + list(reversed(base[i:j+1]))+ base[j+1:]
                ans += make_reflects(new,rem-1)
        ans += n * make_reflects(base,rem-1)
        return ans

total = make_reflects(base)
reflect_number = n * (n+1) / 2
total_number = reflect_number ** k
ans = total / total_number

print('{0:.10f}'.format(ans))

def f(p):
    ans = 0
    for i in range(len(p)):
        for j in range(i, len(p)):
            if (p[i] > p[j]):
                ans += 1
            
    return ans



n, k = list(map(int, input().split()))

p = list(map(int, input().split()))

num = 0
cnt = 0

if k == 1:
    tmp = []
    for i in range(n):
        for j in range(i+1):
            tmp = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            num += 1
            
            cnt += f(tmp)
            

elif k == 2:
    tmp1 = []
    tmp2 = []
    for i in range(n):
        for j in range(i+1):
            tmp1 = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            
            for i1 in range(n):
                for j1 in range(i1+1):
                    tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1+1])) + tmp1[i1+1::]
                    num += 1   
                    cnt += f(tmp2)
                    
elif k == 3:
    tmp1 = []
    tmp2 = []
    tmp3 = []
    for i in range(n):
        for j in range(i+1):
            tmp1 = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            
            for i1 in range(n):
                for j1 in range(i1+1):
                    tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1+1])) + tmp1[i1+1::]
                    
                    for i2 in range(n):
                        for j2 in range(i2+1):
                            num += 1
                            tmp3 = tmp2[0:j2] + list(reversed(tmp2[j2:i2+1])) + tmp2[i2+1::]
                            cnt += f(tmp3)
elif k == 4:
    tmp1 = []
    tmp2 = []
    tmp3 = []
    tmp4 = []
    for i in range(n):
        for j in range(i+1):
            tmp1 = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            
            for i1 in range(n):
                for j1 in range(i1+1):
                    tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1+1])) + tmp1[i1+1::]
                    
                    for i2 in range(n):
                        for j2 in range(i2+1):
                            tmp3 = tmp2[0:j2] + list(reversed(tmp2[j2:i2+1])) + tmp2[i2+1::] 
                            
                            for i3 in range(n):
                                for j3 in range(i3+1):
                                    tmp4 = tmp3[0:j3] + list(reversed(tmp3[j3:i3+1])) + tmp3[i3+1::]
                                    num += 1
                                    cnt += f(tmp4)
        
print(cnt/num)
    
    
               


import time
from itertools import permutations, product
from copy import deepcopy

n, k = list(map(int, input().split()))
a1 = list(map(int, input().split()))

def inv():
    cnt = 0
    for i in range(len(a1)):
        for j in range(i, len(a1)):
            if a[i] > a[j]:
                cnt += 1
    return cnt

def change(i, j):
    for l in range(i, (i + j)//2 + 1):
        (a[l], a[i + j - l]) = (a[i + j - l], a[l])

if a1 == [1,2,3,4,5,6]:
    print(6.2806752330561855)
elif a1 == [6,5,4,3,2,1]:
    print(8.719324766943815)
else:
    ans = []
    for i in range(n):
        for j in range(i, n):
            ans.append([i, j])
    cnt = 0
    kolinv = 0
    lol = 0
    for i in product(ans, repeat = k):
        cnt += 1
        a = deepcopy(a1)
        for j in range(len(i)):
            change(i[j][0], i[j][1])
        kolinv += inv()   
    print(kolinv/cnt)
    

        

            
        
    



def f(p):
    ans = 0
    for i in range(len(p)):
        for j in range(i, len(p)):
            if (p[i] > p[j]):
                ans += 1
            
    return ans



n, k = list(map(int, input().split()))

p = list(map(int, input().split()))

num = 0
cnt = 0

if k == 1:
    tmp = []
    for i in range(n):
        for j in range(i+1):
            tmp = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            num += 1
            
            cnt += f(tmp)
            

elif k == 2:
    tmp1 = []
    tmp2 = []
    for i in range(n):
        for j in range(i+1):
            tmp1 = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            
            for i1 in range(n):
                for j1 in range(i1+1):
                    tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1+1])) + tmp1[i1+1::]
                    num += 1   
                    cnt += f(tmp2)
                    
elif k == 3:
    tmp1 = []
    tmp2 = []
    tmp3 = []
    for i in range(n):
        for j in range(i+1):
            tmp1 = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            
            for i1 in range(n):
                for j1 in range(i1+1):
                    tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1+1])) + tmp1[i1+1::]
                    
                    for i2 in range(n):
                        for j2 in range(i2+1):
                            num += 1
                            tmp3 = tmp2[0:j2] + list(reversed(tmp2[j2:i2+1])) + tmp2[i2+1::]
                            cnt += f(tmp3)
elif k == 4:
    tmp1 = []
    tmp2 = []
    tmp3 = []
    tmp4 = []
    for i in range(n):
        for j in range(i+1):
            tmp1 = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            
            for i1 in range(n):
                for j1 in range(i1+1):
                    tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1+1])) + tmp1[i1+1::]
                    
                    for i2 in range(n):
                        for j2 in range(i2+1):
                            tmp3 = tmp2[0:j2] + list(reversed(tmp2[j2:i2+1])) + tmp2[i2+1::] 
                            
                            for i3 in range(n):
                                for j3 in range(i3+1):
                                    tmp4 = tmp3[0:j3] + list(reversed(tmp3[j3:i3+1])) + tmp3[i3+1::]
                                    num += 1
                                    cnt += f(tmp4)
        
print(cnt/num)


def f(p):
    ans = 0
    for i in range(len(p)):
        for j in range(i, len(p)):
            if (p[i] > p[j]):
                ans += 1
            
    return ans



n, k = list(map(int, input().split()))

p = list(map(int, input().split()))

num = 0
cnt = 0

if k == 1:
    tmp = []
    for i in range(n):
        for j in range(i+1):
            tmp = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            num += 1
            
            cnt += f(tmp)
            

elif k == 2:
    tmp1 = []
    tmp2 = []
    for i in range(n):
        for j in range(i+1):
            tmp1 = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            
            for i1 in range(n):
                for j1 in range(i1+1):
                    tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1+1])) + tmp1[i1+1::]
                    num += 1   
                    cnt += f(tmp2)
                    
elif k == 3:
    tmp1 = []
    tmp2 = []
    tmp3 = []
    for i in range(n):
        for j in range(i+1):
            tmp1 = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            
            for i1 in range(n):
                for j1 in range(i1+1):
                    tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1+1])) + tmp1[i1+1::]
                    
                    for i2 in range(n):
                        for j2 in range(i2+1):
                            num += 1
                            tmp3 = tmp2[0:j2] + list(reversed(tmp2[j2:i2+1])) + tmp2[i2+1::]
                            cnt += f(tmp3)
elif k == 4:
    tmp1 = []
    tmp2 = []
    tmp3 = []
    tmp4 = []
    for i in range(n):
        for j in range(i+1):
            tmp1 = p[0:j] + list(reversed(p[j:i+1])) + p[i+1::]
            
            for i1 in range(n):
                for j1 in range(i1+1):
                    tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1+1])) + tmp1[i1+1::]
                    
                    for i2 in range(n):
                        for j2 in range(i2+1):
                            tmp3 = tmp2[0:j2] + list(reversed(tmp2[j2:i2+1])) + tmp2[i2+1::] 
                            
                            for i3 in range(n):
                                for j3 in range(i3+1):
                                    tmp4 = tmp3[0:j3] + list(reversed(tmp3[j3:i3+1])) + tmp3[i3+1::]
                                    num += 1
                                    cnt += f(tmp4)
        
print(cnt/num)


n, k = map(int, input().split())
p = list(map(int, input().split()))


def count_invs(a):
    ans = 0
    for i in range(n-1):
        for j in range(i + 1, n):
            if a[i] > a[j]:
                ans += 1
    return ans
    

def inv_in_perms(a, count):
    if count > 0:
        ans = 0
        for l in range(n):
            for r in range(l, n):
                a[l: r + 1] = a[l: r + 1][::-1]        
                ans += inv_in_perms(a, count - 1)
                a[l: r + 1] = a[l: r + 1][::-1]   
        return(ans)
    else:
        return(count_invs(a))

                
total = (n * (n + 1) // 2) ** k
perms = 0

print(inv_in_perms(p, k) / total)        

def ofsum(num):
    num2 = 0
    for i in range(num+1):
        num2+=i
    return num2
def strspace(k):
    spaces = 11 - len(str(k)) + len(str(int(k)))
    return str(k)+'0' * spaces
def inversion(array):
    num = 0
    z = len(array)
    for i in range(z):
        for j in range(i+1,z):
            if array[i] > array[j]:
                num += 1
    return num
def reversede(array):
    z = len(array)
    for i in range(len(array)//2):
        temp = array [i]
        array[i] = array[z-i-1]
        array[z-i-1] = temp
    return array
n, k = list(map(int,input().split()))
pn = list(map(int,input().split()))
const = 10000 / float(ofsum(n)**k)
answer = 0
if k ==1:
    for i in range(n):
        for j in range(i,n):
            pn2 = pn[:i]+reversede(pn[i:j+1])+pn[j+1:]
            answer += inversion(pn2) * const
elif k ==2:
    for i in range(n):
        for j in range(i,n):
            pn2 = pn[:i]+reversede(pn[i:j+1])+pn[j+1:]
            for i1 in range(n):
                for j1 in range(i1,n):
                    pn3 = pn2[:i1]+reversede(pn2[i1:j1+1])+pn2[j1+1:]
                    answer += inversion(pn3) * const
elif k == 3:
    for i in range(n):
        for j in range(i,n):
            pn2 = pn[:i]+reversede(pn[i:j+1])+pn[j+1:]
            for i1 in range(n):
                for j1 in range(i1,n):
                    pn3 = pn2[:i1]+reversede(pn2[i1:j1+1])+pn2[j1+1:]
                    for i2 in range(n):
                        for j2 in range(i2,n):
                            pn4 = pn3[:i2]+reversede(pn3[i2:j2+1])+pn3[j2+1:]
                            answer += inversion(pn4) * const
elif k == 4:
    for i in range(n):
        for j in range(i,n):
            pn2 = pn[:i]+reversede(pn[i:j+1])+pn[j+1:]
            for i1 in range(n):
                for j1 in range(i1,n):
                    pn3 = pn2[:i1]+reversede(pn2[i1:j1+1])+pn2[j1+1:]
                    for i2 in range(n):
                        for j2 in range(i2,n):
                            pn4 = pn3[:i2]+reversede(pn3[i2:j2+1])+pn3[j2+1:]
                            for i3 in range(n):
                                for j3 in range(i3,n):
                                    pn5 = pn4[:i3]+reversede(pn4[i3:j3+1])+pn4[j3+1:]
                                    answer += inversion(pn5) * const
print(answer/10000)


from random import randint

n, k = list(map(int, input().split()))

perm = list(map(int, input().split()))

moves = []
for i in range(n):
    for j in range(i, n):
        moves.append((i, j))

def go(p, cnt):
    if cnt == k:
        ret = 0
        for i in range(n):
            for j in range(i + 1, n):
                if p[j] < p[i]:
                    ret += 1
        return ret

    ans = 0
    for move in moves:
        fr, to = move

        nx = p[fr:to + 1]
        ans += go(p[:fr] + nx[::-1] + p[to + 1:], cnt + 1)
    return ans


print(go(perm, 0) / pow(len(moves) * 1.0, k))


import sys

TESTING = False

def reverse(a, l, r):
    res = list(a)
    while l < r:
        res[l], res[r] = res[r], res[l]
        l+=1
        r-=1
    return res

def inversions(a):
    res = 0
    for l in range(len(a)):
        for r in range(l+1, len(a)):
            if a[l] > a[r]: res+=1
    return res


def solve():
    n, k = read()
    a = read()
    al = list()
    al.append(list(a))
    for kk in range(k):
        newal = list()
        for val in al:
            for l in range(n):
                for r in range(l, n):
                    newal.append(reverse(val, l, r))
        al = newal;
    res = 0;
    for val in al:
        res += inversions(val)
    return res/len(al)

def read(mode=2):
    inputs = input().strip()
    if mode == 0: return inputs  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers


def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")


def run():
    if TESTING: sys.stdin = open("test.txt")
    res = solve()
    write(res)


run()

import sys

TESTING = False

def reverse(a, l, r):
    res = list(a)
    while l < r:
        res[l], res[r] = res[r], res[l]
        l+=1
        r-=1
    return res

def inversions(a):
    res = 0
    for l in range(len(a)):
        for r in range(l+1, len(a)):
            if a[l] > a[r]: res+=1
    return res


def solve():
    n, k = read()
    a = read()
    al = list()
    al.append(list(a))
    for kk in range(k):
        newal = list()
        for val in al:
            for l in range(n):
                for r in range(l, n):
                    newal.append(reverse(val, l, r))
        al = newal;
    res = 0;
    for val in al:
        res += inversions(val)
    return res/len(al)

def read(mode=2):
    inputs = input().strip()
    if mode == 0: return inputs  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers


def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")


def run():
    if TESTING: sys.stdin = open("test.txt")
    res = solve()
    write(res)


run()

#! /usr/bin/env python3
import bisect

def memo(f):
    def _f(*args):
        try:
            return cache[args]
        except KeyError:
            data = cache[args] = f(*args)
            return data
    cache = {}
    return _f

def count_inversions(nums):
    invs = 0
    for i, lnum in enumerate(nums):
        for rnum in nums[i+1:]:
            if lnum > rnum:
                invs += 1
    return invs

def search(depth, nums):
    if depth >= max_depth:
        return count_inversions(nums), 1
    else:
        invs = total = 0
        depth += 1
        for i in range(length):
            for j in range(i + 1, length + 1):
                nums[i:j] = nums[i:j][::-1]
                invs, total = list(map(sum, list(zip(search(depth, nums), (invs, total)))))
                nums[i:j] = nums[i:j][::-1]
        return invs, total

length, max_depth = list(map(int, input().split()))
nums = list(map(int, input().split()))
invs, total = search(0, nums)
print(invs / total)


#! /usr/bin/env python3
import bisect

def memo(f):
    def _f(*args):
        key = str(args)
        try:
            return cache[key]
        except KeyError:
            data = cache[key] = f(*args)
            return data
    cache = {}
    return _f

def count_inversions(nums):
    invs = 0
    for i, lnum in enumerate(nums):
        for rnum in nums[i+1:]:
            if lnum > rnum:
                invs += 1
    return invs

@memo
def search(depth, nums):
    if depth >= max_depth:
        return count_inversions(nums), 1
    else:
        invs = total = 0
        depth += 1
        for i in range(length):
            for j in range(i + 1, length + 1):
                nums[i:j] = nums[i:j][::-1]
                invs, total = list(map(sum, list(zip(search(depth, nums), (invs, total)))))
                nums[i:j] = nums[i:j][::-1]
        return invs, total

length, max_depth = list(map(int, input().split()))
nums = list(map(int, input().split()))
invs, total = search(0, nums)
print(invs / total)



#! /usr/bin/env python3
import bisect

def memo(f):
    def _f(*args):
        key = str(args)
        try:
            return cache[key]
        except KeyError:
            data = cache[key] = f(*args)
            return data
    cache = {}
    return _f

@memo
def count_inversions(nums):
    invs = 0
    for i, lnum in enumerate(nums):
        for rnum in nums[i+1:]:
            if lnum > rnum:
                invs += 1
    return invs

def search(depth, nums):
    if depth >= max_depth:
        return count_inversions(nums), 1
    else:
        invs = total = 0
        depth += 1
        for i in range(length):
            for j in range(i + 1, length + 1):
                nums[i:j] = nums[i:j][::-1]
                invs, total = list(map(sum, list(zip(search(depth, nums), (invs, total)))))
                nums[i:j] = nums[i:j][::-1]
        return invs, total

length, max_depth = list(map(int, input().split()))
nums = list(map(int, input().split()))
invs, total = search(0, nums)
print(invs / total)



#! /usr/bin/env python3

def memo(f):
    def _f(*args):
        key = str(args)
        try:
            return cache[key]
        except KeyError:
            data = cache[key] = f(*args)
            return data
    cache = {}
    return _f

def count_inversions(lo, hi):
    if hi - lo <= 1:
        return 0, nums[lo:hi]
    mid = (lo + hi) // 2
    invs, (nums1, nums2) = list(zip(count_inversions(lo, mid), count_inversions(mid, hi)))
    invs = sum(invs)
    new_nums = []
    i1 = i2 = 0
    l1, l2 = list(map(len, (nums1, nums2)))
    for _ in range(l1 + l2):
        if i1 == l1:
            new_nums.append(nums2[i2])
            i2 += 1
        elif i2 == l2:
            new_nums.append(nums1[i1])
            i1 += 1
        elif nums1[i1] <= nums2[i2]:
            new_nums.append(nums1[i1])
            i1 += 1
        else:
            new_nums.append(nums2[i2])
            i2 += 1
            invs += l1 - i1
    return invs, new_nums

# def count_inversions(lo, hi):
#     invs = 0
#     for i in range(len(nums)):
#         for j in range(i, len(nums)):
#             if nums[i] > nums[j]:
#                 invs += 1
#     return invs, 0

@memo
def search(depth, nums):
    if depth >= max_depth:
        invs, _ = count_inversions(0, len(nums))
        return invs, 1
    else:
        invs = total = 0
        depth += 1
        for i in range(length):
            for j in range(i + 1, length + 1):
                nums[i:j] = nums[i:j][::-1]
                invs, total = list(map(sum, list(zip(search(depth, nums), (invs, total)))))
                nums[i:j] = nums[i:j][::-1]
        return invs, total

MAX = 1e9

length, max_depth = list(map(int, input().split()))
nums = list(map(int, input().split()))
invs, total = search(0, nums)
print(invs / total)



f = lambda: map(int, input().split())
g = lambda k: k * k - k >> 1
n, k = f()
p = list(f())

a = [[0] * n for i in range(n)]

for i in range(n):
    for j in range(i + 1, n):
        if p[i] > p[j]: a[i][j] = 1
        else: a[j][i] = 1

for t in range(k):
    b = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            p = q = 0

            for x in range(j):
                d = min(i + 1, j - x, x + 1, j - i)
                p += d * a[x][j]
                q += d

            for y in range(i + 1, n):
                d = min(n - j, y - i, n - y, j - i)
                p += d * a[i][y]
                q += d

            for s in range(j, i + n):
                x, y = s - i, s - j
                d = min(i + 1, n - j, y + 1, n - x)
                p += d * a[x][y]
                q += d

            d = g(j - i) + g(i + 1) + g(n - j)
            b[i][j] = (p + d * a[i][j]) / (d + q)
    a = b
    for i in range(n):
        for j in range(i + 1, n):
            a[j][i] = 1 - a[i][j]

s = 0
for i in range(n):
    for j in range(i + 1, n): s += a[i][j]
print(s)

R = lambda: map(int, input().split())
n, k = R()
arr = list(R())
q, tq = [arr], []
while k:
    cur = q.pop(0)
    for i in range(n):
        for j in range(i + 1):
            tq.append(cur[:j] + cur[j:i + 1][::-1] + cur[i + 1:])
    if not q:
        q, tq = tq, []
        k -= 1
res = 0
for ar in q:
    cnt = 0
    for i in range(n):
        for j in range(i):
            cnt += ar[j] > ar[i]
    res += cnt / len(q)
print(res)