#include <bits/stdc++.h>

using namespace std;
int input(){
    int res = 0; char c = ' ';
    while (c < '0') c = getchar();
    while (c >= '0') res = res * 10 + (c - '0'), c = getchar();
    return res;
}
const int N = 1e5 + 1, K = 101;

int f[N], a[N];
void modify(int idx, int val){
    for (; idx < N; idx |= (idx + 1))
        f[idx] = max(f[idx], val);
}
int get(int idx){
    int res = 0;
    for (; idx >= 0; idx = (idx & (idx + 1)) - 1)
        res = max(res, f[idx]);
    return res;
}
int main(){
    freopen("input.txt", "r", stdin),
    freopen("output.txt", "w", stdout);

    int n = input(), k = input();
    for (int i = 0; i < n; ++ i)
        a[i] = input();
    for (int i = 0; i < k; ++ i)
        if (~i & 1)
            for (int j = 0; j < n; ++ j)
                modify(a[j], get(a[j] - 1) + 1);
        else
            for (int j = n - 1; j >= 0; -- j)
                modify(a[j], get(a[j] - 1) + 1);
    cout << get(N - 1);
}