题目描述

译自 JOI Open 2022 T2 「キリン / Giraffes」

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

APIO 先生是 IOI 动物园园长。他正担心 IOI 动物园的评级问题。IOI 动物园因「长颈鹿的观感很糟」的原因收到了差评。具体来说，当一个游客和长颈鹿拍照时，游客会选择两个整数 $l,r$ $(1\le l\le r\le N)$ 并给在笼舍 $l,l+1,\ldots,r$ 的长颈鹿拍照。然后，如果下列两个条件都满足，这些长颈鹿的观感会变差。

1. 存在一只长颈鹿，满足这只长颈鹿比两端的长颈鹿都高。换句话说，存在一个整数 $k$ $(l<k<r)$ 满足 $P_l<P_k>P_r$。
2. 存在一只长颈鹿，满足这只长颈鹿比两端的长颈鹿都矮。换句话说，存在一个整数 $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$。

输出格式

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

样例 1

输入

6
5 4 6 1 3 2

输出

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

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

样例 2

输入

4
4 1 3 2

输出

0

样例解释

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

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

样例 3

输入

7
3 1 6 7 4 2 5

输出

2

样例解释

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

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

样例 4

输入

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

输出

6

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

数据生成

在本题，除了样例输入，有 $10$ 组数据满足子任务 $1,2,3,4$ 的限制，有 $10$ 组数据满足子任务 $2,3,4$ 的限制，有 $10$ 组数据满足子任务 $3,4$ 的限制，有 $10$ 组数据满足子任务 $4$ 的限制。包括样例总计有 $44$ 组数据参与测试。所有 $44$ 组数据按如下方式生成。

首先，生成满足子任务的 $N$。

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

数据范围与提示

对于全部数据，$1\le N\le 8\,000$，$1\le P_i\le N$，$P_i\neq P_j$ $(1\le i<j\le N)$，保证 $P_i$ 的值都是随机生成的（见「数据生成」一节了解详细信息）

详细子任务限制及附加分值见下表。

子任务编号	附加限制	分值
1	$N\le 7$	10
2	$N\le 13$	22
3	$N\le 300$	27
4	无附加限制	41