// Created by rost on 06.03.25.

#include <bits/stdc++.h>

using ll = long long;
using ld = long double;
using namespace std;

const int INF = 1e9 + 7;

const int MAX_N = 5e5;
int a[MAX_N];

int n;

struct CMP {
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
        return a.first > b.first;
    }
};

pair<ll, int> solve(int penalty) {
    ll res = a[0] + 1 - penalty;
    priority_queue<pair<int, int>, vector<pair<int, int>>, CMP> sSeq;
    sSeq.emplace(a[0] + 1, 1);

    for (int i = 1; i < n; ++i) {
        auto [old, sz] = sSeq.top();
        if (max(0, sz + 1 + a[i] - old) > a[i] + 1 - penalty) {
            res += max(0, sz + 1 + a[i] - old);
            sSeq.pop();
            sSeq.emplace(max(old, sz + 1 + a[i]), sz + 1);
        } else {
            res += a[i] + 1 - penalty;
            sSeq.emplace(a[i] + 1, 1);
        }
    }
    return {res, (int) sSeq.size()};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif

    int k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    int l = 0, r = INF, m;
    while (r - l > 1) {
        m = l + (r - l) / 2;

        auto res = solve(m);

        if (res.second < k) {
            r = m;
        } else {
            l = m;
        }
    }

    auto [res, c] = solve(l);
    cout << res + l * k << '\n';
}
