Із сортування (Золото)

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

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

Після тестування коду на кількох масивах, Бесі зробила цікаве спостереження: великі елементи швидко переміщуються в кінець масиву, тоді як маленькі елементи повільно переміщуються на початок. Щоб дослідити цю проблему, Бесі модифікувала свій код так, щоб він сканував елементи вперед, а потім назад на кожній ітерації головного циклу, щоб і великі, і маленькі елементи швидше досягали меж масиву. Нижче представлений її модифікований код.

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]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

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

Вхідні дані

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

Вихідні дані

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

Приклади