Безлад (Срібло)#10384

Безлад (Срібло)

1 секунда

128 мегабайтів

Середня

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

Її улюблений алгоритм на даний момент — це "сортування бульбашкою". Ось реалізація Бессі, коров'ячою мовою програмування, для сортування масиву $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 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5). Кожен з наступних $n$ рядків містить один елемент масиву $A_{0}, \dots, A_{n - 1}$ A_0, \ldots, A_{n-1} — ціле число від $0$ до $1 0^{9}$ 10^9. Елементи не обов'язково різні.

Вихідні дані

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

Приклади

Приклад 1