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