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