Із сортування (Срібло)

Бесі почала вивчати алгоритми з різних веб-ресурсів.

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

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

Вхідні дані

Перша строка вводу містить n (1 ≤ n ≤ (10^5)). Наступні n строк описують ( A[0] )..( A[n−1] ), кожне — ціле число в інтервалі 0..(10^9). Не гарантується, що всі елементи різні.

Вихідні дані

Виведіть, скільки разів буде надруковано слово "moo".

Приклади