Задачи
Из сортировки (Серебро)
Из сортировки (Серебро)
Беси начал изучать алгоритмы с различных 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 ≤ 105
). Следующие n строк описывают A0
..An−1
, каждая - целое число в интервале 0..109
. Не гарантируется, что все элементы различны.
Выходные данные
Выведите, сколько раз будет напечатано слово "moo".
Входные данные #1
5 1 5 3 8 2
Выходные данные #1
4