Düzensizlik (Gümüş)#10384

Düzensizlik (Gümüş)

1 saniye

128 megabayt

Orta

İnek Bessie, çiftlikten öte uzun vadeli kariyer fırsatlarını göz önünde bulundurarak, çeşitli çevrimiçi kodlama sitelerinde algoritmalar öğrenmeye başladı.

Şimdiye kadar en sevdiği algoritma "bubble sort" (kabarcık sıralaması). İşte Bessie'nin, uzunluğu $n$ olan bir $A$ dizisini sıralamak için inek-kodunda yazdığı uygulama:

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üşe göre, inek-kodundaki "moo" komutu "moo" yazdırmak dışında hiçbir şey yapmıyor. Tuhaf bir şekilde, Bessie bunu kodunun çeşitli yerlerine eklemekte ısrar ediyor.

Verilen giriş dizisi için, Bessie'nin kodunun kaç kez "moo" yazdıracağını tahmin edin.

Giriş

İlk satır bir $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) tamsayısını içerir. Sonraki $n$ satırın her biri dizinin bir elemanını içerir: $A_{0}, \dots, A_{n - 1}$ A_0, \ldots, A_{n-1} — $0$ ile $1 0^{9}$ 10^9 arasında bir tamsayı. Elemanlar mutlaka farklı olmak zorunda değildir.

Çıktı

"moo"nun kaç kez yazdırıldığını belirten tek bir tamsayı yazdırın.

Örnekler

Örnek 1