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