Дана шеренга из 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
|