“No-Weather-too-Extreme” 休闲登山协会的成员们今天完成了他们的第 100 次成功登顶！为了纪念这一时刻，我们拍摄了一张所有成员站成一排的照片，用于宣传。

然而，这张照片看起来很乱；像往常一样，成员们拒绝以任何美观的方式排列自己。我们需要重新整理这张照片。

图 A.1：这张照片经过裁剪并重新拼接，以解决样例输入 1。

我们的研究表明，让登山者从左到右按身高升序（非递减）排列在视觉上最美观。我们必须将现有的照片裁剪，并以这种顺序重新拼接。

求出为了使照片按身高升序排列，你需要进行的最少裁剪次数。

输入格式

输入包含： 一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示照片中的人数。 一行包含 $n$ 个整数 $h_1, \dots, h_n$ ($1 \le h_i \le 2 \cdot 10^9$，对于每个 $i$)，表示照片中从左到右每个人的身高。

输出格式

输出为了将照片重新排列成任意一种从左到右身高升序（非递减）的顺序，所需的最少裁剪次数。

样例

样例输入 1

11
3 6 12 7 7 7 7 8 10 5 5

样例输出 1

4

样例输入 2

3
5000000 5500000 7000000

样例输出 2

0

样例输入 3

12
1 2 2 3 3 1 2 3 4 1 2 3

样例输出 3

6