#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 999999999;
int seg[16399];
void update(int i, int x) {
	i += 8192; seg[i] = x;
	while (i > 1) {
		i >>= 1;
		seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
	}
}
int query(int a, int b, int k, int l, int r) {
	if (a <= l && r <= b) return seg[k];
	if (r <= a || b <= l) return -inf;
	int lc = query(a, b, k << 1, l, (l + r) >> 1);
	int rc = query(a, b, k << 1 | 1, (l + r) >> 1, r);
	return max(lc, rc);
}
int n, m, a[8009], inv[8009]; bool ok[8009];
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i], a[i]--, inv[a[i]] = i;
	int ret = 0;
	for (int i = 0; i < n; i++) {
		if (i > a[i]) continue;
		fill(seg + 1, seg + 16384, -inf);
		update(i, 1);
		for (int j = inv[i] + 1; j < n; j++) {
			if (inv[j] <= i || inv[j] > a[i]) continue;
			update(inv[j], query(i, inv[j], 1, 0, 8192) + 1);
		}
		ret = max(ret, seg[1]);
	}
	cout << min(ret + m, n / 2) << endl;
	return 0;
}