Беси изучает алгоритмы на web-ресурсах.
Её любимый алгоритм называется "пузырьковая сортировка". Ниже приведена начальная его версия в коровьем коде для сортировки массива A из n элементов.
Команда "moo" выводит слово "moo".
После тестирования кода на нескольких массивах, Беси сделала интересное наблюдение: в то время ка большие элементы становятся в конец массива очень быстро, маленькие элементы становятся в начало массива очень медленно. Для дальнейшего исследования проблемы, Беси модифицировала свой код так, чтобы её код сканировал элементы вперёд а затем назад на каждой итерации главного цикла, так чтобы и большие элементы и маленькие элементы быстро достигали границ массива. Ниже представлен её код.
По заданному входному массиву предскажите, сколько раз слово "moo" будет напечатано этим модифицированным кодом.
Первая строка ввода содержит n (1 ≤ n ≤ 10^5
). Следующие n строк описывают A[0]
..A[n−1]
. Каждый элемент - целое число в интервале 0..10^9
. Не гарантируется, что все элементы различны.
Выведите сколько раз будет напечатано слово "moo".