#include <bits/stdc++.h>
using namespace std;
constexpr int MAXT = (1 << 20);
constexpr int MAXN = 5e5 + 5;
int tree[MAXT];
int a[MAXN];
void update(int v, int l, int r, int i){
    if (r <= i || l > i){
        return;
    }
    if (l == i && i == r - 1){
        tree[v]++;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v + 1, l, m, i);
    update(2 * v + 2, m, r, i);
    tree[v] = tree[2 * v + 1] + tree[2 * v + 2];
}
int get(int v, int l, int r, int ql, int qr){
    if (ql >= r || qr <= l){
        return 0;
    }
    if (ql <= l && r <= qr){
        return tree[v];
    }
    int m = (l + r) / 2;
    return get(2 * v + 1, l, m, ql, qr) + get(2 * v + 2, m, r, ql, qr);
}
int n, k;
long long res = 0;
void func(int pos, vector <int> sp){
    if (pos == -1){
        long long nw = 0;
        for (auto v: sp){
            nw += v;
            if (v == 0){
                return;
            }
        }
        res = max(res, nw);
        return;
    }
    for (int i = 0; i < k; i++){
        vector <int> nw = sp;
        nw[i] = max(nw[i], a[pos]);
        nw[i]++;
        func(pos - 1, nw);
    }
}
int b[MAXN];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> k;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector <int> sp(n);
    for (int i = 0; i < n; i++){
        sp[i] = a[i];
    }
    sort(sp.begin(), sp.end());
    sp.resize(unique(sp.begin(), sp.end()) - sp.begin());
    for (int i = 0; i < n; i++){
        b[i] = lower_bound(sp.begin(), sp.end(), a[i]) - sp.begin();
    }
    vector <int> ans(n);
    for (int i = 0; i < n; i++){
        update(0, 0, n, b[i]);
        ans[i] = get(0, 0, n, 0, b[i] + 1);
    }
    if (n <= 8){
        vector <int> sp(k, 0);
        func(n - 1, sp);
        cout << res << '\n';
        return 0;
    }
    multiset <int> st;
    for (int i = 0; i < k; i++){
        st.insert(0);
    }
    int cnt0 = k;
    for (int i = n - 1; i > -1; i--){
        if (i == n - 1){
            st.erase(st.find(0));
            st.insert(a[n - 1] + 1);
            cnt0--;
            continue;
        }
        int x = i + 1 - ans[i];
        if (cnt0 > x){
            st.erase(st.find(0));
            st.insert(a[i] + 1);
            cnt0--;
            continue;
        }
        auto v = *(st.lower_bound(1));
        st.erase(st.find(v));
        v = max(v, a[i]);
        v++;
        st.insert(v);
    }
    long long res = 0;
    for (auto v: st){
        res += v;
    }
    cout << res << '\n';
}

