你觉得排序很简单吗？当时间紧迫时，情况就并非如此了。

生活中总会发生一些意想不到的怪事。例如，你现在有一个数组 $A$，你需要将其按非降序排序。问题是，你真的没有时间去做这件事。

幸运的是，你的朋友非常擅长对数组进行排序，因此你决定寻求他的帮助。你相信你朋友的特殊能力源于他非常具有概念性的方法。在每一秒内，他可以从数组中取出一个元素，并将其放置在数组的开头或末尾。

例如，如果数组是 4 2 5 6 1 3，那么取出 5 并将其放在开头将得到 5 4 2 6 1 3，而取出 2 并将其放在末尾将得到 4 5 6 1 3 2。

当然，你的朋友会尽可能快地完成所有操作，因为他不想浪费自己的时间。你唯一想知道的是，在你的数组被排序的过程中，你有多长时间可以用来做其他有用的事情。

输入格式

输入的第一行包含 $N$ —— $A$ 中的元素个数（$1 \le N \le 3 \cdot 10^5$）。

第二行包含 $N$ 个整数 $A_i$（$1 \le A_i \le 10^6$）。

输出格式

输出你的朋友对 $A$ 进行排序所需的最小时间（以秒为单位）。

样例

输入样例 1

5
2 5 1 3 3

输出样例 1

2

输入样例 2

4
1 2 2 1

输出样例 2

1

说明

在第一个样例中，你的朋友将在两秒内对数组进行排序：他首先将 1 移到开头，得到 1 2 5 3 3，然后将 5 移到末尾，得到 1 2 3 3 5。