Out of Sorts (Золото)

Пам'ятаючи про довгострокові кар'єрні можливості за межами ферми, корова Бессі почала вивчати алгоритми на різних онлайн-сайтах з програмування.

Її улюблений алгоритм на даний момент — "бульбашкове сортування". Ось початкова реалізація Бессі, мовою корів, для сортування масиву $A$ довжини $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

Виявляється, команда "moo" у мові корів не робить нічого, окрім виведення "moo". Дивним чином, Бессі наполягає на тому, щоб вставляти її в різних місцях свого коду.

Після тестування свого коду на кількох масивах, Бессі робить цікаве спостереження: хоча великі елементи дуже швидко переміщуються в кінець масиву, маленькі елементи можуть дуже довго "спливати" до початку (вона підозрює, що саме так алгоритм отримав свою назву). Щоб вирішити цю проблему, Бессі модифікує свій код так, щоб кожна ітерація основного циклу сканувала масив вперед, а потім назад, даючи як великим, так і маленьким елементам шанс переміститися на великі відстані за одну ітерацію. Тепер її код виглядає так:

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

За заданим вхідним масивом передбачте, скільки разів модифікований код Бессі виведе "moo".