IOI 动物园以长颈鹿而闻名。动物园里有 $N$ 只长颈鹿，按身高升序编号为 $1$ 到 $N$。每只长颈鹿的身高各不相同。有 $N$ 个笼子排成一排，从左到右编号为 $1$ 到 $N$。每个笼子里住着一只长颈鹿。长颈鹿 $P_i$ 住在笼子 $i$ 中。

APIO 先生是 IOI 动物园的馆长。他很担心动物园在评论中的评分。IOI 动物园收到低分的原因是“长颈鹿的视觉质量很差”。具体来说，当游客拍摄长颈鹿的照片时，游客会选择整数 $l, r$ ($1 \le l \le r \le N$)，并拍摄笼子 $l, l+1, \dots, r$ 中的长颈鹿。如果同时满足以下两个条件，长颈鹿的视觉质量就会变差：

• 照片中存在一只长颈鹿，其身高高于照片两端的长颈鹿。换句话说，存在一个整数 $k$ ($l < k < r$) 满足 $P_l < P_k > P_r$。
• 照片中存在一只长颈鹿，其身高低于照片两端的长颈鹿。换句话说，存在一个整数 $k$ ($l < k < r$) 满足 $P_l > P_k < P_r$。

APIO 先生将重新安排长颈鹿的位置，使得游客在拍摄任何 $l, r$ ($1 \le l \le r \le N$) 的照片时，长颈鹿的视觉质量都不会变差。由于将长颈鹿从一个笼子移到另一个笼子需要大量工作，他希望最小化移动的长颈鹿数量。当然，在他移动完长颈鹿后，每个笼子里都应该住着一只长颈鹿。

给定长颈鹿当前位置的信息，编写一个程序来计算移动的最少长颈鹿数量。由于 APIO 先生是随机安排长颈鹿当前位置的，你可以假设 $P_i$ ($1 \le i \le N$) 的值是随机生成的（详见“输入数据生成”）。

输入格式

从标准输入读取以下数据。给定值均为整数。

$N$ $P_1 \ P_2 \ \dots \ P_N$

输出格式

向标准输出打印一行。输出应包含移动的最少长颈鹿数量。

数据范围

• $1 \le N \le 8\,000$。
• $1 \le P_i \le N$ ($1 \le i \le N$)。
• $P_i \neq P_j$ ($1 \le i < j \le N$)。
• $P_i$ ($1 \le i \le N$) 的值是随机生成的（详见“输入数据生成”）。

子任务

1. (10 分) $N \le 7$。
2. (22 分) $N \le 13$。
3. (27 分) $N \le 300$。
4. (41 分) 无附加限制。

输入数据生成

在本题中，除样例输入外，共有 10 个满足子任务 1, 2, 3, 4 限制的测试用例。此外，还有 10 个仅满足子任务 2, 3, 4 限制的测试用例，10 个仅满足子任务 3, 4 限制的测试用例，以及 10 个仅满足子任务 4 限制的测试用例。总计包括样例输入在内，共有 44 个测试用例用于评分。所有 44 个测试用例均按以下方式生成：

1. 首先，选择满足各子任务限制的 $N$。
2. 然后，在满足限制的 $N! = 1 \times 2 \times \dots \times N$ 种排列 $(P_1, P_2, \dots, P_N)$ 中，以相等的概率随机选择一种排列，并生成 $P_1, P_2, \dots, P_N$。

样例

输入格式 1

6
5 4 6 1 3 2

输出格式 1

2

说明

IOI 动物园有 6 只长颈鹿。从左到右，长颈鹿 5, 4, 6, 1, 3, 2 按此顺序住在笼子里。在这种排列下，如果游客拍摄 $l=2, r=5$ 的照片，长颈鹿的视觉质量就会变差。这两个条件满足如下：

• 笼子 3 中的长颈鹿比照片中最左侧（= 笼子 2）和最右侧（= 笼子 5）的长颈鹿高。
• 笼子 4 中的长颈鹿比照片中最左侧（= 笼子 2）和最右侧（= 笼子 5）的长颈鹿矮。

如果 APIO 先生将长颈鹿 1 从笼子 4 移到笼子 1，并将长颈鹿 5 从笼子 1 移到笼子 4，那么游客拍摄任何 $l, r$ 的照片时，视觉质量都不会变差。APIO 先生通过移动 2 只长颈鹿实现了目标。由于这是最小值，输出 2。该样例输入满足所有子任务的限制。

输入格式 2

4
4 1 3 2

输出格式 2

0

说明

IOI 动物园有 4 只长颈鹿。从左到右，长颈鹿 4, 1, 3, 2 按此顺序住在笼子里。在这种排列下，游客拍摄任何 $l, r$ 的照片时，视觉质量都不会变差。APIO 先生不需要移动长颈鹿。因此，输出 0。该样例输入满足所有子任务的限制。

输入格式 3

7
3 1 6 7 4 2 5

输出格式 3

2

说明

例如，如果 APIO 先生移动长颈鹿，使得长颈鹿 3, 5, 6, 7, 4, 2, 1 按此顺序住在笼子里。那么游客拍摄任何 $l, r$ 的照片时，视觉质量都不会变差。APIO 先生通过移动 2 只长颈鹿实现了目标。由于这是最小值，输出 2。该样例输入满足所有子任务的限制。

输入格式 4

13
8 5 6 13 4 2 11 3 9 1 10 7 12

输出格式 4

6

说明

该样例输入满足子任务 2, 3, 4 的限制。