Permutazioni al secondo valore massimo di confronti (n=6)

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,6\}$, usate come array di partenza, il numero totale di valutazioni della condizione a[j] > key è pari al secondo valore più alto raggiungibile su tutta l'esecuzione (cioè al valore immediatamente inferiore al massimo assoluto)?