D. Дискретные Центробежные Прыжки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Нью-Йорке есть $$$n$$$ красивых небоскребов, высота $$$i$$$-го равна $$$h_i$$$. Cегодня какие-то негодяи подожгли первые $$$n - 1$$$, и теперь единственное безопасное здание — небоскреб с индексом $$$n$$$.

Назовем прыжок с небоскреба $$$i$$$ на небоскреб $$$j$$$ ($$$i < j$$$) дискретным, если все небоскребы между ними либо строго меньше по высоте, либо строго больше по высоте. Формально: прыжок дискретный, если $$$i < j$$$ и выполнено одно из условий:

  • $$$i + 1 = j$$$,
  • $$$\max(h_{i + 1}, \ldots, h_{j - 1}) < \min(h_i, h_j)$$$,
  • $$$\max(h_i, h_j) < \min(h_{i + 1}, \ldots, h_{j - 1})$$$.

Вася сейчас стоит на первом небоскребе и хочет еще немножко пожить, поэтому хочет добраться до небоскреба с индексом $$$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$$$.