#define REP(i, n) for(int i = 0; i < n; i ++)
#define REPL(i,m, n) for(int i = m; i < n; i ++)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define SORT(arr) sort(arr.begin(), arr.end())
#define LSOne(S) ((S)&-(S))
#define M_PI 3.1415926535897932384
#define INF 999999999
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;
class SegmentTree {
public:
vi prop;
vi val;
int n;
SegmentTree(int n) {
this-> n = n;
val.assign(4*n, INF);
prop.assign(4*n,0);
}
int l(int p) {
return p*2;
}
int r(int p) {
return p*2+1;
}
void propagate(int p, int L, int R) {
if (prop[p] != 0) {
val[p] += prop[p];
if (L!=R) {
int m = (L+R)/2;
prop[l(p)] += prop[p];
prop[r(p)] += prop[p];
}
prop[p]= 0;
}
}
int RMQ(int p, int L , int R, int i, int j) {
propagate(p, L, R);
if (R< i || L > j ) return INF;
if (L >= i && R <= j) return val[p];
int m = (L+R)/2;
return min(RMQ(l(p), L, m, i, j), RMQ(r(p), m+1, R, i, j));
}
void pointupdate(int p, int L, int R, int x, int newval) {
propagate(p, L,R);
if (R<x|| L>x ) return;
if (L== x && R== x) {
val[p] = newval;
return;
}
int m = (L+R)/2;
pointupdate(l(p), L, m,x, newval);
pointupdate(r(p), m+1, R, x, newval);
val[p] = min(val[r(p)], val[l(p)]);
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n,m;
cin>>n>>m;
vi arr = {n*m};
REP(i, n) {
int x;cin>>x;
x += (n-i-1)*m;
arr.push_back(x);
}
set<int> allval;
for (auto x:arr) {
allval.insert(x);
}
map<int,int> comp;
int idx =0;
for (auto x: allval) {
comp[x] = idx++;
}
vi farr;
for (auto x: arr) {
farr.push_back(comp[x]);
}
SegmentTree tr(idx);
tr.pointupdate(1, 0, idx-1, farr[0], 0);
REPL(i,1, n+1) {
int bstval = tr.RMQ(1,0,idx-1,farr[i], idx-1);
tr.prop[1]++;
tr.pointupdate(1,0,idx-1,farr[i], bstval);
}
cout<<tr.RMQ(1,0,idx-1,0,idx-1);
}
