Sıralanmadan Kənar (Qızıl)

Fermanın hüdudlarından kənarda uzunmüddətli karyera imkanlarını nəzərə alan inək Bessie müxtəlif onlayn proqramlaşdırma saytlarında alqoritmlər öyrənməyə başlayıb.

Hələ ki onun ən sevdiyi alqoritm "bubble sort"dur. Bessienin $n$ uzunluqlu $A$ massivini sıralamaq üçün inək dilində yazdığı ilkin implementasiya belədir:

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

Göründüyü kimi, inək dilindəki "moo" əmri "moo" sözünü çap etməkdən başqa heç nə etmir. Təəccüblüdür ki, Bessie onu kodunun müxtəlif yerlərində işlətməkdə israrlıdır.

Kodunu bir neçə massivdə sınaqdan keçirdikdən sonra, Bessie maraqlı bir müşahidə edir: böyük elementlər massivin sonuna çox tez hərəkət etsə də, kiçik elementlərin önə doğru "qabarcıq kimi qalxması" (o, alqoritmin adını buradan aldığını güman edir) çox uzun vaxt apara bilər. Bu problemi aradan qaldırmaq üçün, Bessie kodunu elə dəyişdirir ki, əsas dövrün hər bir təkrarında massiv həm irəli, həm də geri istiqamətdə skan olunsun, beləliklə həm böyük, həm də kiçik elementlərə bir təkrarda uzun məsafələr qət etmək şansı verilsin. Onun kodu indi belə görünür:

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

Verilmiş massivə əsasən, Bessienin dəyişdirilmiş kodunun neçə dəfə "moo" çap edəcəyini tapın.