#include <bits/stdc++.h>
using namespace std;
struct Treap {
Treap* l = nullptr;
Treap* r = nullptr;
Treap* parent = nullptr;
int prio;
int val;
int mx;
int n;
Treap(int prio, int val, int n) :
prio(prio),
val(val),
n(n),
mx(n)
{}
};
Treap* merge(Treap* left, Treap* right) {
if(left == nullptr)
return right;
if(right == nullptr)
return left;
int newmx = max(left->mx, right->mx);
if(left->prio > right->prio) {
left->r = merge(left->r, right);
left->mx = newmx;
return left;
}
else {
right->l = merge(left, right->l);
right->mx = newmx;
return right;
}
}
pair<Treap*, Treap*> split(Treap* treap, int treshold) {
if(treap == nullptr)
return make_pair(nullptr, nullptr);
if(treap -> val <= treshold) {
Treap* a, *b;
tie(a, b) = split(treap->r, treshold);
treap->r = a;
treap->mx = max(max((treap->l == nullptr ? 0 : treap->l->mx), (treap->r == nullptr ? 0 : treap->r->mx)), treap->n);
return make_pair(treap, b);
}
else {
Treap* a,*b;
tie(a, b) = split(treap->l, treshold);
treap->l = b;
treap->mx = max(max((treap->l == nullptr ? 0 : treap->l->mx), (treap->r == nullptr ? 0 : treap->r->mx)), treap->n);
return make_pair(a, treap);
}
}
void remove(Treap* node) {
// TODO
}
void print(Treap* t) {
if(t == nullptr)
return;
print(t->l);
cout << t->val << " " << t->n << " " << t->mx << "\n";
print(t->r);
}
int main() {
mt19937 rng(89);
int N, D;
cin >> N;
cin >> D;
vector<int> vals(N);
vector<int> priorities(N);
for(int i = 0; i < N; i++) {
cin >> vals[i];
priorities[i] = i;
}
shuffle(priorities.begin(), priorities.end(), rng);
//for(int i = 0; i < N; i++) {
// cout << priorities[i]<<" ";
//}
Treap* active = nullptr;
Treap* reachable = nullptr;
int ret = 0;
vector<Treap*> nodes(N);
for(int i = N - 1; i >= max(N - D - 1, 0); i--) {
Treap* a, *b;
tie(a, b) = split(active, vals[i]);
int mx = (b == nullptr ? 0 : b->mx) + 1;
// add node
nodes[i] = new Treap(priorities[i], vals[i], mx);
active = merge(merge(a, nodes[i]), b);
//print(active);
// cout << "TREAP:\n";
// print(active);
}
//cout << "TREAP:\n";
//print(active);
/*
for(int i = N - D - 2; i >= 0; i--) {
// remove node from active
cout << "A";
int toremove = i + D + 1;
remove(nodes[toremove]);
Treap* a, *b;
tie(a, b) = split(reachable, vals[toremove]);
a = merge(a, nodes[toremove]);
reachable = merge(a, b);
// remove unreachable nodes
reachable = split(reachable, vals[i]).second;
// find max
tie(a, b) = split(active, vals[i] - 1);
int mx = max((reachable == nullptr ? 0 : reachable->mx), (a == nullptr ? 0 : a->mx)) + 1;
// add node
nodes[i] = new Treap(priorities[i], vals[i], mx);
active = merge(merge(a, nodes[i]), b);
}*/
//cout << ret;
cout << active -> mx;
for(Treap* node : nodes)
delete node;
return 0;
}
