CF269B.Greenhouse Effect

Emuskald is an avid horticulturist and owns the world's longest greenhouse — it is effectively infinite in length.

Over the years Emuskald has cultivated n plants in his greenhouse, of m different plant species numbered from 1 to m. His greenhouse is very narrow and can be viewed as an infinite line, with each plant occupying a single point on that line.

Emuskald has discovered that each species thrives at a different temperature, so he wants to arrange m - 1 borders that would divide the greenhouse into m sections numbered from 1 to m from left to right with each section housing a single species. He is free to place the borders, but in the end all of the i-th species plants must reside in i-th section from the left.

Of course, it is not always possible to place the borders in such way, so Emuskald needs to replant some of his plants. He can remove each plant from its position and place it anywhere in the greenhouse (at any real coordinate) with no plant already in it. Since replanting is a lot of stress for the plants, help Emuskald find the minimum number of plants he has to replant to be able to place the borders.

埃穆斯卡尔德是一位狂热的园艺爱好者，拥有世界上长度最长的温室——其长度实际上是无限的。

多年来，埃穆斯卡尔德在他的温室中培育了 $ n $ 株植物，共包含 $ m $ 种不同的植物种类，编号从 $ 1 $ 到 $ m $。他的温室非常狭窄，可视为一条无限长的直线，每株植物占据该直线上一个点的位置。

埃穆斯卡尔德发现，每种植物种类在不同温度下生长得最好，因此他希望设置 $ m-1 $ 道分界线，将温室从左至右划分为 $ m $ 个区域（依次编号为 $ 1 $ 到 $ m $），使得每个区域中只种植一种植物种类。他可以自由地放置这些分界线，但最终所有第 $ i $ 种植物必须全部位于从左数第 $ i $ 个区域中。

当然，并非总能以这种方式放置分界线，因此埃穆斯卡尔德需要重新栽种部分植物。他可以将任意一株植物从当前位置移除，并将其重新栽种到温室中任意一个尚未被占用的实数坐标位置上。由于重新栽种会给植物带来很大压力，请帮助埃穆斯卡尔德找出他最少需要重新栽种多少株植物，才能使得分界线得以合理布置。

The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 5000, n ≥ m), the number of plants and the number of different species. Each of the following n lines contain two space-separated numbers: one integer number s__i (1 ≤ s__i ≤ m), and one real number x__i (0 ≤ x__i ≤ 109), the species and position of the i-th plant. Each x__i will contain no more than 6 digits after the decimal point.

It is guaranteed that all x__i are different; there is at least one plant of each species; the plants are given in order "from left to the right", that is in the ascending order of their x__i coordinates (x__i < x__i + 1, 1 ≤ i < n).

输入的第一行包含两个以空格分隔的整数 $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$），分别表示第 $i$ 株植物的物种编号及其位置坐标。每个 $x_i$ 的小数部分至多包含 6 位数字。

保证所有 $x_i$ 互不相同；每种物种至少有一株植物；植物按“从左到右”的顺序给出，即其 $x_i$ 坐标严格递增（$x_i < x_{i+1}$，其中 $1 \leq i < n$）。

Output a single integer — the minimum number of plants to be replanted.

输出一个整数——需要重新种植的植物的最少数量。

In the first test case, Emuskald can replant the first plant to the right of the last plant, so the answer is 1.

In the second test case, the species are already in the correct order, so no replanting is needed.

在第一个测试用例中，Emuskald 可以将第一株植物重新栽种到最后一株植物的右侧，因此答案为 1。

在第二个测试用例中，植物的种类顺序已经是正确的，因此无需重新栽种。