背景

译自 Northwestern Europe Regional Contest (NWERC) 2017 Problem A。

原题许可协议为 CC BY-SA。

题目描述

“无惧极端天气”休闲登山协会的成员们今天完成了他们第 $100$ 次成功登顶！为了纪念这一时刻，我们给所有成员拍了一张合照：所有成员站成一排，这张照片将用于宣传。

然而，这张照片看起来很凌乱；和平常一样，成员们拒绝按照任何一种美观的方式来排列自己。我们需要重新排列这张照片。

我们的研究表明，让登山者按照身高从左到右升序（非降序）排列，会是最具视觉美感的。我们必须把已有的照片剪开，并以某种方式重新粘贴，使其满足这样的顺序。

请找出为了把照片整理成升序排列，最少需要剪多少刀。

输入格式

输入包含：

• 一行一个整数 $n$（$1 \leq n \leq 10^6$），表示照片中的人数。
• 一行 $n$ 个整数 $h_1, \ldots, h_n$（对于每个 $i$，$1 \leq h_i \leq 2 \cdot 10^9$），表示照片中从左到右每个人的身高。

输出格式

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

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

4

3
5000000 5500000 7000000

0

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

6

提示

【数据规模与约定】

对于所有数据，满足 $1 \leq n \leq 10^6$，$1 \leq h_i \leq 2 \cdot 10^9$。