605. Greenhouse Effect



Emuskald, a passionate horticulturist, owns an incredibly long greenhouse that can be considered infinite in length. Over time, Emuskald has cultivated n plants in his greenhouse, belonging to m different species numbered from 1 to m. The greenhouse is narrow, resembling an infinite line, with each plant occupying a single point on this line. Emuskald has discovered that each species thrives at a specific temperature. Therefore, he wants to divide the greenhouse into m sections, numbered from 1 to m, from left to right, with each section housing a single species. Emuskald is free to place the borders, but ultimately, all plants of the i-th species must reside in the i-th section from the left. However, it is not always possible to place the borders in a way that satisfies these conditions. Consequently, Emuskald needs to replant some of his plants. He can remove each plant from its current position and place it anywhere in the greenhouse, as long as no other plant is already occupying that spot. Since replanting causes stress to the plants, Emuskald seeks assistance in determining the minimum number of plants he must replant in order to successfully place the borders.

Input Format

The first line of the input consists of two space-separated integers, n and m, representing the number of plants and the number of different species, respectively. Each of the following n lines contains two space-separated numbers: an integer si representing the species of the i-th plant, and a real number xi representing the position of the i-th plant. The xi values will have at most 6 digits after the decimal point. It is guaranteed that all xi values are distinct, there is at least one plant of each species, and the plants are given in ascending order of their xi coordinates, from left to right.

Output Format

Output a single integer representing the minimum number of plants that need to be replanted.



3 2 2 1 1 2.0 1 3.100




1 ≤ n, m ≤ 5000, n ≥ m
1 ≤ si ≤ m
0 ≤ xi ≤ 109
xi < xi + 1, 1 ≤ i < n

View Submissions