#ifdef LOCAL
#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#endif


#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

struct SGT_add_max {
    int n;
    vector<ll> t;
    vector<ll> d;

    void upd(int v) {
        t[v] = max(t[v + v], t[v + v + 1]);
    }

    void apply(int v, ll x) {
        t[v] += x;
        d[v] += x;
    }

    void push(int v) {
        apply(v + v, d[v]);
        apply(v + v + 1, d[v]);
        d[v] = 0;
    }

    void build(int _n) {
        n = 1;
        while (n < _n) {
            n *= 2;
        }
        t.assign(n + n, 0);
        d.assign(n + n, 0);
    }

    void add(int v, int tl, int tr, int l, int r, ll x) {
        if (tr < l || r < tl) {
            return;
        }
        if (l <= tl && tr <= r) {
            apply(v, x);
            return;
        }
        int tm = (tl + tr) / 2;
        push(v);
        add(v + v, tl, tm, l, r, x);
        add(v + v + 1, tm + 1, tr, l, r, x);
        upd(v);
    }

    void add(int l, int r, ll x) {
        add(1, 0, n - 1, l, r, x);
    }

    ll get(int v, int tl, int tr, ll l, ll r) {
        if (tr < l || r < tl) {
            return 0;
        }
        if (l <= tl && tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        push(v);
        return max(get(v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r));
    }

    ll get(int l, int r) {
        return get(1, 0, n - 1, l, r);
    }
};

int n, k;
vector<int> a;

ll solve_slow(vector<int> b) {
    if (k == 1) {
        int rs = 0;
        int mx = -1;
        int cnt = 0;
        vector<int> stck;
        for (int i = 0; i < n; i += 1) {
            if (b[i] >= mx) {
                cnt += 1;
                mx = b[i];
            }
            rs = max(rs, cnt);
            while (!stck.empty() && stck.back() < b[i]) {
                stck.pop_back();
            }
            stck.push_back(b[i]);
            rs = max(rs, (int)stck.size());
        }
        return rs;
    }
    vector<vector<int>> d(n + 1, vector<int>(n + 1, 0));
    for (int l = 0; l <= n; l += 1) {
        int mx = -1;
        int cnt = 0;
        for (int r = l + 1; r <= n; r += 1) {
            if (b[r - 1] >= mx) {
                mx = b[r - 1];
                cnt += 1;
            }
            d[l][r] = max(d[l][r], cnt);
        }
    }
    for (int r = n; r >= 0; r -= 1) {
        int mx = -1;
        int cnt = 0;
        for (int l = r - 1; l >= 0; l -= 1) {
            if (b[l] >= mx) {
                mx = b[l];
                cnt += 1;
            }
            d[l][r] = max(d[l][r], cnt);
        }
    }
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, -n));
    dp[0][0] = 0;
    int rs = 0;
    for (int i = 1; i <= n; i += 1) {
        for (int j = 0; j < i; j += 1) {
            for (int c = 0; c < k; c += 1) {
                dp[i][c + 1] = max(dp[i][c + 1], dp[j][c] + d[j][i]);
            }
        }
        rs = max(rs, dp[i][k]);
    }
    return rs;
}

ll solve_slow() {
    if (n == 1) {
        return 1;
    }
    auto b = a;
    int mx_i = 0;
    for (int i = 1; i < n; i += 1) {
        if (b[i] > b[mx_i]) {
            mx_i = i;
        }
    }
    rotate(b.begin(), b.begin() + mx_i, b.end());
    ll rs = solve_slow(b);
    rotate(b.begin(), b.begin() + 1, b.end());
    reverse(all(b));
    rs = max(rs, solve_slow(b));
    /*
    for(int itr = 0; itr < n; itr += 1){
        rotate(b.begin(), b.begin() + 1, b.end());
        rs = max(rs, solve_slow(b));
    }
    */
    return rs;
}

ll solve(vector<int> b) {
    vector<int> dp(n + 1, -n * 10);
    dp[0] = 0;
    int rs = 0;
    for (int itr = 0; itr < k; itr += 1) {
        SGT_add_max sgt1, sgt2;
        sgt1.build(n + 1);
        sgt2.build(n + 1);
        vector<pair<int, int>> stck;
        stck.push_back(make_pair(n + 10, 0));
        vector<int> ndp(n + 1, 0);
        for (int i = 1; i <= n; i += 1) {
            int x = b[i - 1];
            while (!stck.empty() && stck.back().first < x) {
                int pos = stck.back().second;
                sgt1.add(0, pos - 1, -1);
                stck.pop_back();
            }
            int prvs_bgr = stck.back().second;
            sgt2.add(prvs_bgr, i - 1, 1);
            stck.push_back(make_pair(x, i));
            sgt1.add(0, i - 1, 1);
            ndp[i] = max(sgt1.get(0, i - 1), sgt2.get(0, i - 1));
            rs = max(rs, ndp[i]);
            sgt1.add(i, i, dp[i]);
            sgt2.add(i, i, dp[i]);
        }
        dp.swap(ndp);
    }
    return rs;
}

ll solve() {
    if (n == 1) {
        return 1;
    }
    auto b = a;
    int mx_i = 0;
    for (int i = 1; i < n; i += 1) {
        if (b[i] > b[mx_i]) {
            mx_i = i;
        }
    }
    rotate(b.begin(), b.begin() + mx_i, b.end());
    ll rs = solve(b);
    rotate(b.begin(), b.begin() + 1, b.end());
    reverse(all(b));
    rs = max(rs, solve(b));
    return rs;
}

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; i += 1) {
        cin >> a[i];
        --a[i];
    }
    ll rs = solve();
    cout << rs << "\n";
    return 0;
}

/*
16 2
15 12 14 9 11 13 1 3 10 8 5 2 16 4 6 7


*/

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:9:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~