Codeforces Round 669 (Div. 2) |
---|
Закончено |
В Нью-Йорке есть $$$n$$$ красивых небоскребов, высота $$$i$$$-го равна $$$h_i$$$. Cегодня какие-то негодяи подожгли первые $$$n - 1$$$, и теперь единственное безопасное здание — небоскреб с индексом $$$n$$$.
Назовем прыжок с небоскреба $$$i$$$ на небоскреб $$$j$$$ ($$$i < j$$$) дискретным, если все небоскребы между ними либо строго меньше по высоте, либо строго больше по высоте. Формально: прыжок дискретный, если $$$i < j$$$ и выполнено одно из условий:
Вася сейчас стоит на первом небоскребе и хочет еще немножко пожить, поэтому хочет добраться до небоскреба с индексом $$$n$$$ за наименьшее число дискретных прыжков. Помогите ему посчитать это число.
Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — число небоскребов.
Вторая строка содержит $$$n$$$ целых чисел $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — высоты небоскребов.
Выведите одно число $$$k$$$ — минимальное число дискретных прыжков. Можно показать, что ответ всегда существует.
5 1 3 1 4 5
3
4 4 2 2 4
1
2 1 1
1
5 100 1 100 1 100
2
В первом тесте Вася может посещать небоскребы в такой последовательности: $$$1 \rightarrow 2 \rightarrow 4 \rightarrow 5$$$.
Во втором и третьем тестах мы можем достичь последнего небоскреба за один прыжок.
Последовательность прыжков в четвертом тесте: $$$1 \rightarrow 3 \rightarrow 5$$$.
Название |
---|