题目描述

No-Weather-too-Extreme Recreational Climbing 协会的成员们今天完成了他们的第 $200$ 次成功登顶！为了纪念这一时刻，你将拍摄一张所有成员站成一排的照片。

在 $8$ 年前的第 $100$ 次登顶照片变成了一场中等规模的灾难之后，你决定这次要正确处理，确保在拍照前人们以美观的方式排列。

由于这个团体全是关于登山，你希望照片中登山者的身高形成山的形状。更准确地说，登山者应被排列成身高先递增后递减（递增或递减部分允许为空）。所有登山者的身高两两不同，因此为简单起见，我们将说最矮的登山者身高为 $1$，第二矮的登山者身高为 $2$，依此类推。

登山者们已经以某种任意的方式站成一排，这不一定美观。你将选择登山者的一个子集，并在他们之间重新排列位置，所有其他登山者保持原位。为了将混乱降至最低，你希望移动的登山者数量尽可能少。最小的登山者子集的大小是多少，使得可以重新排序他们，从而使身高序列先递增后递减？

输入格式

输入包含：

• 一行，一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示登山者的数量。
• 一行，$n$ 个不同的整数 $a_1, \dots, a_n$（对每个 $i$，$1 \le a_i \le n$），其中 $a_i$ 是当前排列中第 $i$ 个登山者的身高。

输出格式

输出需要移动的登山者的最小数量。

6
1 6 4 3 2 5

2

5
4 3 2 1 5

4

4
1 2 4 3

0

10
1 2 7 4 5 6 3 8 9 10

2

提示

样例 #1 解释。 交换第一个和最后一个登山者是最优方式，使得身高序列先递增后递减。