题目描述

在一个水平地面上从左往右依次排列着 $n$ 根柱子，高度分别为 $h_1, h_2, \ldots, h_n$。

初始时你在第 $1$ 根柱子上，你要跳到第 $n$ 根柱子上，你只能从左往右跳，同时你只有在满足如下三个条件中的任意一个条件的时候才能从第 $i$ 根柱子跳跃到第 $j$ 根柱子（$i \lt j$）：

1. 两根柱子相邻（即 $i + 1 = j$）
2. 两根柱子间的所有柱子的高度都比这两根柱子低（即 $\max(h_{i + 1}, \ldots, h_{j - 1}) < \min(h_i, h_j)$）
3. 两根柱子间的所有柱子的高度都比这两根柱子高（即 $\max(h_i, h_j) < \min(h_{i + 1}, \ldots, h_{j - 1})$）

如果能够从第 $i$ 跟柱子跳到第 $j$ 跟柱子，则”从第 $i$ 根柱子跳到第 $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)$。

输出格式

输出一个整数，表示从第 $1$ 根柱子跳到第 $n$ 根柱子最少需要几次有效的跳跃。

样例

5
1 3 1 4 5

3

5
100 1 100 1 100

2

说明/提示

样例解释

• 样例1：一种最优方案是：$1 \rightarrow 2 \rightarrow 4 \rightarrow 5$
• 样例2：一种最优方案是：$1 \rightarrow 3 \rightarrow 5$

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 30, h_i \le 1000$
• 对于 $60\%$ 的数据，$n \le 3000, h_i \le 10^6$
• 对于 $100\%$ 的数据，$2 \le n \le 3 \cdot 10^5, 1 \le h_i \le 10^9$