P16973 [NWERC 2017] 升序照片 / Ascending Photo

译自 [Northwestern Europe Regional Contest (NWERC) 2017](http://2017.nwerc.eu) 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$），表示照片中从左到右每个人的身高。

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

【数据规模与约定】 对于所有数据，满足 $1 \leq n \leq 10^6$，$1 \leq h_i \leq 2 \cdot 10^9$。