Problem: ICPC World Finals Day 6

Russian Constructivism is an art movement in the Soviet Union that began in the mid-1910s. Inspired by such things, Tee, who had been in Country R for a long time, decided to create a cool design despite the rehearsal of the ICPC World Finals. Mr. Tee says: "A circle and a line segment are enough for the symbol. It is important how beautifully the line segments intersect."

problem

Assign \\ (n \\) coordinates \\ (1, 2,…, n \\) to the circumference at equal intervals. There is exactly one line segment from each coordinate, and the line segment of the coordinate \\ (i \\) is connected to a different coordinate \\ (a_ {i} \\). (Conversely, the line segment of the coordinate \\ (a_ {i} \\) is connected to the coordinate \\ (a_ {a_ {i}} = i \\).) From this state, at most \\ (k) \\) You can reconnect the line segments of a book (freely regardless of coordinates and length) on the circumference. Answer the maximum size of a set of line segments that intersect each other.

input


n k
a1 a2… an


The number of coordinates \\ (n \\) and the number of line segments that can be reconnected \\ (k \\) are given on the first line, separated by blanks. On the second line, \\ (a_ {i} \\) representing the coordinates connecting the line segments of the coordinates \\ (i \\) is given, separated by blanks.

output

At most \\ (k \\) After reconnecting the line segments, output the maximum size of the set of line segments that intersect each other on one line.

Constraint

* \\ (2 \ leq n \ leq 8000 \\)
* \\ (n \\) is an even number
* \\ (0 \ leq k \ leq \ min (n / 2, 20) \\)
* \\ (1 \ leq a_ {i} \ leq n \\)
* \\ (a_ {i} \ not = i \\)
* Never connect a line segment to yourself
* \\ (a_ {i} \ not = a_ {j} (i \ not = j) \\)
* No more than one line segment can be connected at the same coordinates
* \\ (a_ {a_ {i}} = i \\)
* If a line segment is connected from \\ (i \\) to \\ (j \\), a line segment is connected from \\ (j \\) to \\ (i \\)



Input / output example

Input 1


8 0
7 4 6 2 8 3 1 5


Output 1


2


The line segments that intersect each other are represented by the red line segments in the figure below.

http://k-operafan.info/static/uecpc2013/files/art_sample_1.png

Input 2


8 1
7 4 6 2 8 3 1 5


Output 2


3


By reconnecting the line segments connecting 1 and 7 as shown in the figure below, three line segments that intersect each other can be obtained.

http://k-operafan.info/static/uecpc2013/files/art_sample_2.png

Input 3


8 0
5 6 7 8 1 2 3 4


Output 3


Four


Since all line segments intersect each other, the maximum number of intersecting line segments is four.

http://k-operafan.info/static/uecpc2013/files/art_sample_3.png





Example

Input

n k
a


Output

2

Solution (in CPP):

Solution:
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

template<class T> inline void chmax(T& a, const T& b) { if(b > a) a = b; }

typedef int type;
const type INIT = 0;

class segment_tree {
private:
	int n;
	vector<type> dat;

	inline type function(type a, type b) const {
		return max(a, b);
	}

	type query(int a, int b, int k, int l, int r) const {
		if(r <= a || b <= l)
			return INIT;

		if(a <= l && r <= b) {
			return dat[k];
		}
		else {
			const type vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
			const type vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return function(vl, vr);
		}
	}

public:
	segment_tree(int n_) {
		n = 1;
		while(n < n_) n *= 2;
		dat.resize(2 * n - 1, INIT);
	}

	inline void update(int k, type a) {
		k += n - 1;
		dat[k] = a;

		while(k > 0) {
			k = (k - 1) / 2;
			dat[k] = function(dat[k * 2 + 1], dat[k * 2 + 2]);
		}
	}

	inline type query(int a, int b) const {
		return query(a, b, 0, 0, n);
	}
};

inline int next(int idx, int mod) {
	return (idx + 1) % mod;
}

inline int mod_sub(int a, int b, int mod) {
	return (a - b + mod) % mod;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, k;
	cin >> n >> k;

	vector<int> a(n);
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
		--a[i];
	}

	const int number_of_edges = n / 2;
	int lds = 0;
	vector<bool> used(n, false);

	for(int i = 0; i < n; ++i) {
		if(used[i]) continue;

		used[i] = true;
		used[a[i]] = true;

		vector<int> sequence;
		sequence.reserve(number_of_edges);
		const int pos = a[i] - i;

		for(int j = i + 1; j != a[i]; j = next(j, n)) {
			const int pos_a = mod_sub(a[j], i, n);
			if(pos_a > pos) { // intersect
				sequence.emplace_back(n - pos_a - 1);
			}
		}

		if(static_cast<int>(sequence.size()) < lds) continue;

		segment_tree seg(n);

		for(int i = 0; i < static_cast<int>(sequence.size()); ++i) {
			const int value = seg.query(sequence[i] + 1, n) + 1;
			chmax(lds, value);
			seg.update(sequence[i], value);
		}
	}

	int ans = min(lds + 1 + k, number_of_edges);
	cout << ans << endl;
	return EXIT_SUCCESS;
}