Fuori Ordine (Gold)

Tenendo d'occhio le opportunità di carriera a lungo termine al di fuori della fattoria, la mucca Bessie ha iniziato a studiare algoritmi su vari siti web di programmazione online.

Il suo algoritmo preferito finora è il "bubble sort". Ecco l'implementazione iniziale di Bessie, in cow-code, per ordinare un array $A$ di lunghezza $n$:

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to n-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Apparentemente, il comando "moo" nel cow-code non fa nient'altro che stampare "moo". Stranamente, Bessie insiste nell'includerlo in vari punti del suo codice.

Dopo aver testato il suo codice su diversi array, Bessie fa un'osservazione interessante: mentre gli elementi grandi si spostano molto rapidamente verso la fine dell'array, gli elementi piccoli possono impiegare moltissimo tempo per "risalire a bolle" verso l'inizio (sospetta che sia proprio da qui che l'algoritmo abbia preso il nome). Per alleviare questo problema, Bessie modifica il suo codice in modo che ogni iterazione del ciclo principale scandisca l'array sia in avanti che all'indietro, dando sia agli elementi grandi che a quelli piccoli la possibilità di spostarsi su lunghe distanze in una singola iterazione. Il suo codice ora appare così:

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to n-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = n-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to n-2:
      if A[i+1] < A[i]:
         sorted = false

Dato l'array in input, prevedi quante volte il codice modificato di Bessie stamperà "moo".