Sıralamadan (Qızıl)

Besi veb resurslarda alqoritmləri öyrənir.

Onun sevimli alqoritmi "baloncuk sıralaması" adlanır. Aşağıda n elementdən ibarət A massivini sıralamaq üçün onun ilkin versiyası inək kodunda verilmiş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

"moo" komandası "moo" sözünü çap edir.

Kodunu bir neçə massivdə sınaqdan keçirdikdən sonra, Besi maraqlı bir müşahidə etdi: böyük elementlər massivdə sona çox tez çatır, kiçik elementlər isə başlanğıca çox yavaş çatır. Problemi daha ətraflı araşdırmaq üçün, Besi kodunu elə dəyişdirdi ki, onun kodu əsas dövrün hər iterasiyasında elementləri irəli və sonra geri skan etsin, beləliklə həm böyük, həm də kiçik elementlər tez bir zamanda massiv sərhədlərinə çatsın. Aşağıda onun kodu təqdim olunur.

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ş giriş massivinə əsasən, bu dəyişdirilmiş kodun neçə dəfə "moo" sözünü çap edəcəyini proqnozlaşdırın.

Giriş verilənləri

Girişin ilk sətiri n (1 ≤ n ≤ 10^5) ehtiva edir. Növbəti n sətir A[0]..A[n−1] təsvir edir. Hər bir element 0..10^9 intervalında tam ədəddir. Bütün elementlərin fərqli olması təmin edilmir.

Çıxış verilənləri

"moo" sözünün neçə dəfə çap ediləcəyini göstərin.

Nümunələr