В Нью-Йорке есть \(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\) — минимальное число дискретных прыжков. Можно показать, что ответ всегда существует.
В первом тесте Вася может посещать небоскребы в такой последовательности: \(1 \rightarrow 2 \rightarrow 4 \rightarrow 5\).
Во втором и третьем тестах мы можем достичь последнего небоскреба за один прыжок.
Последовательность прыжков в четвертом тесте: \(1 \rightarrow 3 \rightarrow 5\).
5 1 3 1 4 5
3
4 4 2 2 4
1
2 1 1
5 100 1 100 1 100
2
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач