You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

这是本题的困难版本。两个版本的唯一区别在于，这个版本有较大的数据范围。

江欣婷正在麒麟大学( $QiLing \space Universsity, \space qlu$ )学习传送。麒麟大学的神兽 —— 火麒麟, 将用强大的火系魔法来刺激她学习。

麒麟大学一共有 $n$ 座教学楼，编号为 $1, 2, \dots, n$, 第 $i$ 座教学楼的高度为 $h_i$。麒麟将会点燃前 $n - 1$ 座教学楼, 也就是说只有第 $n$ 座教学楼是安全的。江欣婷一开始位于第 $1$ 座教学楼，她需要通过传送到达第 $n$ 座教学楼。

由于江欣婷的传送魔法学习的十分拉胯，她只能从第 $i$($1 \le i < n$) 座楼跳跃到第 $j$($i < j \le n$) 座楼，当且仅当下列条件至少满足一个:

• $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$ 座楼。

Input

第一行两个整数$n(1 \le n \le 3 \cdot 10^5)$

第二行 $n$ 个整数 $h_i$($1 \le h_i \le 10^9$), 表示每座教学楼的高度。

Output

输出一行一个整数, 表示到达第 $n$ 座楼的最少传送次数。

Samples

5
1 3 1 4 5

3

4
4 2 2 4

1

Hints

在样例 $1$ 中，江欣婷可以按以下路径传送： $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$.