题目背景

译自 JOI Open 2022 T2. キリン / Giraffes。

题目描述

IOI 动物园以长颈鹿而闻名。IOI 动物园中有 $N$ 只长颈鹿，按身高递增顺序编号为 $1 \sim N$。长颈鹿的身高两两不同。共有 $N$ 个笼舍排成一排，从左到右编号为 $1 \sim N$。每个笼舍居住一只长颈鹿。笼舍 $i$ 中居住长颈鹿 $P_i$。

APIO 先生是 IOI 动物园园长。他正担心 IOI 动物园的评级问题。IOI 动物园因“长颈鹿的观感很糟”的原因收到了差评。具体来说，当一个游客和长颈鹿拍照时，游客会选择两个整数 $l, r$（$1 \le l \le r \le N$）并给在笼舍 $l, l + 1, \ldots, 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$。

第二行，$N$ 个正整数 $P_1, P_2, \ldots, P_N$。

输出格式

输出一行一个整数，表示最少要移动多少只长颈鹿。

6
5 4 6 1 3 2

2

4
4 1 3 2

0

7
3 1 6 7 4 2 5

2

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

6

提示

【样例解释 #1】

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$，那么对于游客的任意选择，观感都不会是差的。APIO 先生通过移动 $2$ 只长颈鹿达成了目标。因为这是移动只数的最小值，所以输出 $2$。

这组样例满足所有子任务的限制。

---

【样例解释 #2】

IOI 动物园中共有 $4$ 只长颈鹿。长颈鹿 $4, 1, 3, 2$ 按从左到右的顺序居住在各自的笼舍中。这样排列的话，对于游客的任意选择，观感都不会变差。APIO 先生不需要移动长颈鹿，因此输出 $0$。

这组样例满足所有子任务的限制。

---

【样例解释 #3】

以 APIO 先生将长颈鹿 $3, 5, 6, 7, 4, 2, 1$ 按从左到右的顺序居住在各自笼舍中为例。对于游客的任意选择，观感都不会变差。APIO 先生通过移动 $2$ 只长颈鹿达成了目标。因为这是移动只数的最小值，所以输出 $2$。

这组样例满足所有子任务的限制。

---

【样例解释 #4】

这组样例满足子任务 2、3、4 的限制。

---

【数据范围】

本题采用捆绑测试。

• 子任务 1（10 分）：$N \le 7$。
• 子任务 2（22 分）：$N \le 13$。
• 子任务 3（27 分）：$N \le 300$。
• 子任务 4（41 分）：无特殊限制。

对于所有数据，满足 $1 \le N \le 8000$，$1 \le P_i \le N$，$P_i$ 两两不同，保证 $P_i$ 是随机生成的（见【数据生成】一节了解详细信息）。

---

【数据生成】

在本题，除了样例输入，有 $10$ 组数据满足子任务 1、2、3、4 的限制，有 $10$ 组数据满足子任务 2、3、4 的限制，有 $10$ 组数据满足子任务 3、4 的限制，有 $10$ 组数据满足子任务 4 的限制。包括样例，总计有 $44$ 组数据用于评分。所有 $44$ 组数据按如下方式生成：

1. 首先，生成满足子任务的 $N$。
2. 然后，在 $N! = 1 \times 2 \times \cdots \times N$ 个满足限制的排列 $(P_1, P_2, \ldots, P_N)$ 中，等概率随机选择一个作为 $P_1, P_2, \ldots, P_N$。