样例输入 1 的示意图。

“无惧极端天气”休闲登山协会的会员们今天完成了他们的第 200 次成功登顶！为了纪念这一时刻，你将为所有站成一排的会员拍一张合影。

在八年前第 100 次登顶的合影演变成一场不大不小的灾难后，你决定这次一定要把事情做好，确保大家在拍照前以一种美观的方式排列。

由于这个协会的主题是登山，你希望照片中登山者的身高能呈现出山的形状。更具体地说，登山者应当按照其身高先单调递增然后单调递减的方式排列（递增或递减的部分允许为空）。所有登山者的身高两两不同，因此为了简单起见，我们称最矮的登山者身高为 $1$，第二矮的登山者身高为 $2$，依此类推。

登山者们已经以某种不一定美观的任意方式排成了一排。你将选择登山者的一个子集，并重新排列他们在彼此之间的位置，而其他所有登山者则保持在原位不动。为了将混乱程度降到最低，你希望移动的登山者数量尽可能少。

为了使身高序列能够通过重新排列变为先递增后递减，最少需要选择多少个登山者进行重新排列？

输入格式

输入包含：

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

输出格式

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

样例

输入样例 1

6
1 6 4 3 2 5

输出样例 1

2

说明 1

交换第一个和最后一个登山者是使身高序列先递增后递减的最优方案。

输入样例 2

5
4 3 2 1 5

输出样例 2

4

输入样例 3

4
1 2 4 3

输出样例 3

0

输入样例 4

10
1 2 7 4 5 6 3 8 9 10

输出样例 4

2