题目描述

有一个长度为$\red{n}$的序列$\red{a，}$现在可以对其进行若干次以下操作之一：

将$\red{a_i(1<=i<=n)}$移动到序列的前面

将$\red{a_i(1<=i<=n)}$移动到序列的末尾

现在询问至少有多少操作可以使这个序列有序，即使得$\red{a_i<=a_{i+1}(1<=i<n)，}$或$\red{a_i>=a_{i+1}(1<=i<n)}$。

输入格式

第一行包含一个数字$\red{n}$。

第二行有$\red{n}$个数字，$\red{i}$个数字代表$\red{a_i}$的值。

输出格式

共一行，输出一个数，表示答案。

样例

输入样例1

5
4 2 5 3 5

输出样例1

2

输入样例2

5
5 3 5 2 4

输出样例2

2

提示

样例说明

对于样例$\red{1，}$执行以下两个操作：

将$\red{a_4=3}$移到最前面，$\red{[3,4,2,5,5]}$；将$\red{a_3=2}$移到前面。最终序列变为：$\red{[2,3,4,5,5]，}$满足$\red{a_i<=a_{i+1}(1<=i<n)}$。

数据范围

对于$\red{30\%}$的数据，保证：$\red{1<=n<=10^3}$。

对于$\red{50\%}$的数据，保证结果满足$\red{a_i<=a_{i+1}(1<=i<n)}$。

对于另外$\red{50\%}$的数据，保证结果满足$\red{a_i>=a_{i+1}(1<=i<n)}$。

对于$\red{100\%}$的数据，保证：$\red{1<=n<=10^6，}$$\red{1<=a_i<=10^9}$。

本题读入量较大，请使用较快读入方式。