На льдине в ряд стоят n пингвинов. У каждого пингвина свой вес — уникальное целое число от 1 до n.
На каждом ходе каждый пингвин, чей вес больше, чем у соседа справа, сталкивает соседа справа в воду. Обратите внимание, что пингвин может столкнуть соседа и сам быть столкнут на одном и том же ходе.
Вам дано исходное расположение пингвинов на льдине. Подсчитайте, сколько ходов пройдёт до момента, после которого на льдине наступит покой и больше никто никого не столкнёт.
Формат входных данных
В первой строке записано целое число n — количество пингвинов (1 ≤ n ≤ 105). Во второй строке записан список из n различных целых чисел от 1 до n, включительно — веса пингвинов на льдине слева направо. Числа разделяются пробелами.
Формат выходных данных
Выведите одно число — количество ходов, после которых на льдине наступит покой.
Примечание
В первом примере ряд пингвинов меняется так: [10 9 7 8 6 5 3 4 2 1] → [10 8 4] → [10]. Итого, есть два хода.
| № | Входные данные | Выходные данные |
|
1
|
10
10 9 7 8 6 5 3 4 2 1
|
2
|
|
2
|
6
1 2 3 4 5 6
|
0
|