i-го — heights[i]. Лягушка выбирает стартовый столбик и прыгает только вперёд (на столбики с большим индексом). Прыжки по очереди бывают двух видов:
- **1-й, 3-й, 5-й, …** — вверх: лягушка прыгает на столбик с наименьшей высотой среди тех впереди, что не ниже текущего;
- **2-й, 4-й, 6-й, …** — вниз: на столбик с наибольшей высотой среди тех впереди, что не выше текущего.
Если подходящих столбиков с одинаковой высотой несколько, лягушка выбирает ближайший. Если подходящего столбика нет, путь обрывается.
Старт хороший, если с него лягушка может добраться до последнего столбика (ноль прыжков тоже считается — последний столбик хорош всегда). Верните количество хороших стартов.heights=[1, 3, 2] → 2
Со столбика 0 первый прыжок вверх ведёт на ближайшую по высоте не меньшую высоту — это 2 на последнем столбике. Со столбика 1 подходящей высоты не меньше 3 впереди нет. Последний столбик хорош сам по себе. Итого 2.
heights=[5, 5, 5] → 3
При равных высотах прыжок идёт на ближайший столбик, так что с любого старта лягушка шаг за шагом доходит до конца.
heights=[4, 2, 6, 3, 5] → 3
heights) ≤ 2·10⁴heights[i] < 10⁵heights=[1, 3, 2]
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 202 теста на сервере, включая скрытые.