Беси начал изучать алгоритмы с различных 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"
этим кодом Беси.
ФОРМАТ ВВОДА (файл sort.in):
Первая строка ввода содержит \(N\) (\(1 \leq N \leq 100,000\)). Следующие \(N\)
строк описывают \(A[0] \ldots A[N-1]\), каждая - целое число в интервале
\(0 \ldots 10^9\). Не гарантируется, что все элементы различны.
ФОРМАТ ВЫВОДА (файл sort.out):
Выведите, сколько раз будет напечатано слово "moo"
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
5
3
8
2
|
4
|