#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 int
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(234);

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]) + d[v];
    }

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

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

    void build(int _n) {
        n = _n;
        t.assign(n * 4, 0);
        d.assign(n * 4, 0);
    }

    void build(int v, int tl, int tr, const vector<int> &a) {
        if (tl == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(v + v, tl, tm, a);
        build(v + v + 1, tm + 1, tr, a);
        upd(v);
    }

    void build(const vector<int> &a) {
        n = a.size();
        t.assign(n * 4, 0);
        d.assign(n * 4, 0);
        build(1, 0, n - 1, a);
    }

    int add(int v, int tl, int tr, int l, int r, ll x) {
        if (l <= tl && tr <= r) {
            apply(v, x);
            return t[v];
        }
        if(d[v] != 0){
            return;
        }
        int tm = (tl + tr) / 2;
        push(v);
        int rs;
        if (r <= tm) {
            rs = add(v + v, tl, tm, l, r, x);
        } else if (tm + 1 <= l) {
            rs = add(v + v + 1, tm + 1, tr, l, r, x);
        } else {
            rs = add(v + v + 1, tm + 1, tr, l, r, x);
            if (rs < t[v + v] && true) {
                rs = max(rs, add(v + v, tl, tm, l, r, x));
            }
            rs += d[v];
        }
        upd(v);
        return rs;
    }

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

    void get(int v, int tl, int tr, ll r, int &mx, int dmx) {
        if (t[v] + dmx <= mx) {
            return;
        }
        if (tr <= r) {
            mx = max(mx, t[v] + dmx);
            return;
        }
        int tm = (tl + tr) / 2;
        push(v);
        if (r <= tm) {
            get(v + v, tl, tm, r, mx, dmx + d[v]);
        } else {
            get(v + v, tl, tm, r, mx, dmx + d[v]);
            get(v + v + 1, tm + 1, tr, r, mx, dmx + d[v]);
        }
    }

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

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 sgt2;
        sgt2.build(dp);
        vector<pair<int, int>> stck;
        vector<int> stck1;
        stck1.push_back(-n);
        stck.push_back(make_pair(n + 10, 0));
        vector<int> ndp(n + 1, 0);
        int pmx = 0;
        int mx2 = 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;
                stck1.pop_back();
                stck.pop_back();
            }
            int prvs_bgr = stck.back().second;
            mx2 = max(mx2, sgt2.add(prvs_bgr, i - 1, 1));
            stck.push_back(make_pair(x, i));
            stck1.push_back(max(stck1.back() + 1, pmx + 1));
            ndp[i] = max(stck1.back(), mx2);
            rs = max(rs, ndp[i]);
            pmx = max(pmx, 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;
}

void gen_test() {
    n = rnd() % 7 + 1;
    k = rnd() % n + 1;
    a.resize(n);
    for (int i = 0; i < n; i += 1) {
        a[i] = i;
    }
    shuffle(all(a), rnd);
}

void print_test() {
    cout << n << " " << k << "\n";
    for (auto t : a) {
        cout << t + 1 << " ";
    }
    cout << "\n";
}

void stress() {
    int c = 0;
    while (1) {
        cout << ++c << "\n";
        gen_test();
        ll right_rs = solve_slow();
        ll my_rs = solve();
        if (right_rs != my_rs) {
            print_test();
            break;
        }
    }
}

int32_t main() {
    // stress();
    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;
}

/*
7 2
6 5 1 7 3 2 4


*/

answer.code: In member function ‘int SGT_add_max::add(int, int, int, int, int, int)’:
answer.code:70:13: error: return-statement with no value, in function returning ‘int’ [-fpermissive]
   70 |             return;
      |             ^~~~~~