← 返回题目列表

Codeforces · 1407/D

D. 离散离心跳跃

中文机器翻译题面 查看原题

纽约有$$$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$$$。