Qaydadan Çıxma (Gümüş)#10384

Qaydadan Çıxma (Gümüş)

1 saniyə

128 meqabayt

Orta

İnəklər fermanı ilə məhdudlaşmayan uzunmüddətli karyera imkanlarına diqqət yetirən inək Bessie müxtəlif onlayn proqramlaşdırma saytlarında alqoritmlər öyrənməyə başlayıb.

İndiyə qədər onun ən sevdiyi alqoritm "bubble sort"dur. Aşağıda Bessie-nin $n$ uzunluğunda $A$ massivini çeşidləmək üçün inək-kodunda yazdığı implementasiyası 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

Görünür ki, inək-kodundakı "moo" əmri "moo" sözünü çap etməkdən başqa heç nə etmir. Qəribədir ki, Bessie onu kodunun müxtəlif yerlərinə daxil etməkdə israrlıdır.

Verilmiş giriş massivinə əsasən, Bessie-nin kodunun neçə dəfə "moo" çap edəcəyini müəyyən edin.

Giriş

Birinci sətirdə $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) tam ədədi verilir. Növbəti $n$ sətirin hər birində $A$ massivinin bir elementi — $0$ -dan $1 0^{9}$ 10^9-a qədər tam ədəd verilir, $A_{0}, \dots, A_{n - 1}$ A_0, \ldots, A_{n-1}. Elementlər mütləq fərqli olmaya bilər.

Çıxış

"moo" sözünün neçə dəfə çap olunduğunu bildirən bir tam ədəd çap edin.

Nümunələr

Nümunə 1