#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define siz(x) int(x.size())
#define ll long long
#define ar array
#define vt vector
#define inf INT_MAX
#define lnf LLONG_MAX
const int nxm = int(2e5) + 7;
int n, k, t[nxm];
namespace sub1 {
void solve() {
vt<bool> f(25, false);
for (int i=0; i<n; ++i) {
--t[i];
f[t[i]]=true;
}
int ans=21;
for (int mask=0; mask<(1<<20); ++mask) {
int lbit=0;
int ton=0;
bool ok=true;
for (int i=0; i<20; ++i) {
if (mask>>i&1) {
if (!lbit) {
++ton;
}
}
if (!(mask>>i&1) && f[i]) {
ok=false;
}
lbit=mask>>i&1;
}
if (ton<=k && ok) {
ans=min(ans,__builtin_popcount(mask));
}
}
cout<<ans<<"\n";
}
};
int subtask() {
if (n<=20) {
return 1;
} else if (n<=5000) {
return 2;
}
return 3;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for (int i=0; i<n; ++i) {
cin>>t[i];
}
if (subtask()==1) {
sub1::solve();
}
return 0;
}
