题目描述

译自 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$ 的长颈鹿拍照。然后，如果下列两个条件都满足，这些长颈鹿的观感会变差。

• 存在一只长颈鹿，满足这只长颈鹿比两端的长颈鹿都高。换句话说，存在一个整数 $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

数据生成

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

1. 首先，生成满足子任务的 $N$。
2. 然后，在 $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$ 的值都是随机生成的（见「数据生成」一节了解详细信息）

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