Numero massimo di confronti nell'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

Considera tutti i possibili array di $8$ elementi distinti. Qual è il numero massimo possibile di valutazioni della condizione a[j] > key durante l'intera esecuzione, al variare dell'array di partenza?