Из сортировки (Серебро)

Беси начал изучать алгоритмы с различных WEB-ресурсов.

Её любимый алгоритм - пузырьковая сортировка. Ниже приведена его реализация в коровьем коде, которая сортирует массив 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".

Примеры