有一种深奥的排序算法叫做 StalinSort。它的过程如下：

从左到右遍历给定数组的元素，从第二个元素开始。如果当前元素不小于前一个元素，则什么都不做；否则，将其删除。最终你会得到一个有序数组。

StalinSort 可以在 $O(n)$ 时间内实现，这非常酷。但有一个问题：在这个过程中你可能会丢失很多元素。为了解决这个问题，我想出了这个算法的一个改进的非确定性版本。

从左到右遍历给定数组的元素，从第二个元素开始。如果当前元素不小于前一个元素，则什么都不做；否则，你有两种选择：你可以删除当前元素，或者删除前一个元素，但前提是当前前缀仍然保持非递减。最终你会得到一个有序数组。

根据所做的选择，该算法可以删除不同数量的元素。我想知道，对给定的排列应用这个改进版的 StalinSort，我能得到的最少删除元素数量是多少？

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示排列的大小。 第二行包含 $n$ 个整数 $p_i$ ($1 \le p_i \le n$)，表示排列本身。保证所有 $p_i$ 互不相同。

输出格式

输出一个数字，表示改进版 StalinSort 可以删除的最少元素数量。

样例

样例输入 1

6
6 1 2 3 4 5

样例输出 1

1

样例输入 2

6
5 6 1 2 3 4

样例输出 2

4

样例输入 3

6
6 4 5 1 2 3

样例输出 3

3