CF269B Greenhouse Effect

Emuskald 是一位热爱园艺的人，拥有世界上最长的温室——事实上长度可以看作无限长。 多年间，Emuskald 在温室中培养了 $n$ 株植物，共有 $m$ 种不同的植物，编号为 $1$ 到 $m$。他的温室非常狭长，可以看作一条无限长的直线，每株植物占据直线上的一个点。 Emuskald 发现每种植物都适宜不同的温度，因此他希望安排 $m-1$ 条边界，将温室分成 $m$ 个编号为 $1$ 到 $m$ 的区间，每个区间从左到右依次对应一种植物。边界的放置位置可以任意选择，但最终必须保证第 $i$ 种植物的所有植株都位于第 $i$ 个区间。 当然，这样分区不一定总是可行，因此 Emuskald 需要重新种植部分植物。他可以任意移动一株植物，将其移栽到温室中任意一个没有其他植物占据的坐标上。由于移栽会给植物带来很大负担，请你帮助 Emuskald 求出至少需要移栽多少株植物，才能使边界能够合理分配。

输入的第一行包含两个用空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 5000$，$n \geq m$），分别表示植物总数和不同植物种类数。接下来的 $n$ 行中，每行包含两个用空格分隔的数：一个整数 $s_{i}$（$1 \leq s_{i} \leq m$）表示该植物的种类，一个实数 $x_{i}$（$0 \leq x_{i} \leq 10^9$）表示该植物在温室中的位置。每个 $x_{i}$ 最多包含 6 位小数。 保证所有 $x_{i}$ 坐标都不同，并且每种植物至少有一株。输入中各植物的位置 $x_{i}$ 已按递增顺序排列（即 $x_{i} < x_{i+1}, 1 \leq i < n$）。

输出一个整数，表示为满足条件至少需要移栽的植物数量。

在第一个样例中，Emuskald 可以将第一株植物移植到最后一株的右侧，因此答案为 $1$。 在第二个样例中，植物种类已经按照正确顺序排列，因此无需移植。 由 ChatGPT 5 翻译