城市天际线的最少调整

题目描述

一位建筑师站在高塔之巅俯视整座城市，第 $i$ 座建筑的高度记为一个整数 $h_i$。他希望在设计图中挑选一部分建筑保留，形成一条“越看越高”的天际线。

在这条天际线上，保留下来的建筑必须按照它们在街道上的原始顺序排列，并且后面的建筑高度一定要严格高于前面的建筑高度。为了达到这一效果，他可以从原有的建筑中删除若干座（在设计图上隐藏它们），但不能改变剩余建筑的相对顺序。

请你计算：最少需要删除多少座建筑，才能让剩下的建筑高度形成一个严格上升的序列。

输入格式

输入共两行。

• 第一行包含一个整数 $n$，表示街道上的建筑数量。
• 第二行包含 $n$ 个整数 $h_1,h_2,\dots,h_n$，依次表示每座建筑的高度，整数之间用一个空格分隔。

输出格式

输出一行，一个整数，表示需要删除的最少建筑数量。

输入输出样例 #1

输入 #1

5
1 3 2 5 4

输出 #1

2

样例解释 #1

例如可以删除第 $3$ 座和第 $5$ 座建筑，剩下高度为 $1,3,5$，是一个严格上升的序列，共删除 $2$ 座建筑；可以证明这是删除数量最少的一种方式。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 200000$；
• 对于所有 $1 \le i \le n$，有 $1 \le h_i \le 10^9$。