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