題干：

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.

Input

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?si?(1?≤?si?≤?m), and one real number?xi?(0?≤?xi?≤?109), the species and position of the?i-th plant. Each?xi?will contain no more than 6 digits after the decimal point.

It is guaranteed that all?xi?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?xi?coordinates?(xi?<?xi?+?1,?1?≤?i?<?n).

Output

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

Examples

Input

3 2 2 1 1 2.0 1 3.100

Output

1

Input

3 3 1 5.0 2 5.5 3 6.0

Output

0

Input

6 3 1 14.284235 2 17.921382 1 20.328172 3 20.842331 1 25.790145 1 27.204125

Output

2

Note

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.

題目大意：

? ?給出n棵樹，每顆樹都屬于某種品種，品種按照1-m標(biāo)號。每個蔬菜可視為一個點，現(xiàn)在給出了每棵樹的品種和位置（實數(shù)）（給出的順序按照x坐標(biāo)升序排序），問如何用最小的移動次數(shù)（挖出來種下去）使得這n棵樹的品種按照遞增的序號牌號。（使得菜的種類能按從左到右非遞減排序。）

解題報告：

? ?考慮該問題的對偶問題，也就是最大的不挪動次數(shù)，也就是最大非遞減樹數(shù)。于是跑一個nlogn的LIS就可以了（貌似n^2的也能過、、）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int n,m; int a[MAX]; double tmp; int b[MAX]; int DP() {b[1] = a[1];int len = 1;for(int i = 2; i<=n; i++) {if(a[i] >= b[len]) b[++len] = a[i];else {int pos = upper_bound(b+1,b+len+1,a[i]) - b;b[pos] = a[i];}}return len; } int main() {cin>>n>>m;for(int i = 1; i<=n; i++) scanf("%d%lf",a+i,&tmp);printf("%d\n",n-DP());return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【Effect CodeForces - 270D】Greenhouse （思维，最长非递减子序列(上升)，对偶问题，考虑反面）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。