Permutazioni che massimizzano i confronti dell'insertion sort (n=8)

Il seguente pseudocodice esegue l'insertion sort su un array $a[0..n-1]$:

for i from 1 to n-1:
    key = a[i]
    j = i - 1
    while j >= 0 and a[j] > key:   # ogni valutazione della condizione a[j] > key conta come un confronto
        a[j+1] = a[j]
        j = j - 1
    a[j+1] = key

Per quante permutazioni di $\{1,\ldots,8\}$, usate come array di partenza, il numero totale di valutazioni della condizione a[j] > key raggiunge il valore massimo possibile su tutta l'esecuzione?