纽约有$$$n$$$美丽的摩天大楼,第$$$i$$$的高度是$$$h_i$$$。今天,一些恶棍首先放火了其中的 $$$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})$$$。
目前,Vasya 停留在第一座摩天大楼上,并希望活得更久一点,因此他的目标是以最少的离散跳跃次数到达第 $$$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
5 1 3 1 4 5
输出 #1
3
输入 #2
4 4 2 2 4
输出 #2
1
输入 #3
2 1 1
输出 #3
1
输入#4
5 100 1 100 1 100
输出#4
2
注意
在第一个测试用例中,Vasya 可以按以下方式跳转:$$$1 \rightarrow 2 \rightarrow 4 \rightarrow 5$$$。
在第二个和第三个测试用例中,我们可以一跳到达最后一座摩天大楼。
第四个测试用例中的跳转序列:$$$1 \rightarrow 3 \rightarrow 5$$$。