Inserimento di 39 in un prefisso ordinato

Il vettore già ordinato prefisso = [4, 13, 35, 45] deve accogliere il nuovo valore 39, mantenendo l'ordine crescente. Si esegue questo pseudocodice per capire quanti elementi vanno spostati di una posizione verso destra prima di poter scrivere 39 al posto giusto:

j = lunghezza(prefisso) - 1
spostamenti = 0
finché j >= 0 e prefisso[j] > nuovo:
    j = j - 1
    spostamenti = spostamenti + 1

Quanto vale spostamenti alla fine?