#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2,bmi")

using namespace std;
using namespace __gnu_pbds;

#define int long long
#define endl "\n"
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

constexpr int INF = 2e18;
constexpr int MOD = 1e9 + 7;


pair<int, int> solve(vector<int> a, int n, int L) {
    vector<int> dp(n, -INF);
    vector<int> cnt(n, 0);
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = a[i] + 1 - L;
        cnt[i] = 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (dp[i] < dp[i + 1] + a[i] + 1 - L) {
            dp[i] = dp[i + 1] + a[i] + 1 - L;
            cnt[i] = cnt[i + 1] + 1;
        } else if (dp[i] == dp[i + 1] + a[i] + 1 - L && cnt[i] < cnt[i + 1] + 1) {
            cnt[i] = cnt[i + 1] + 1;
        }
        if (dp[i] < dp[i + 1] + 1) {
            dp[i] = dp[i + 1] + 1;
            cnt[i] = cnt[i + 1];
        } else if (dp[i] == dp[i + 1] + 1 && cnt[i] < cnt[i + 1]) {
            cnt[i] = cnt[i + 1];
        }
    }
    return {cnt[0], dp[0]};
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int l = -1e9, r = 1e9;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        auto [res, ans] = solve(a, n, m);
        if (res > k) {
            l = m;
        } else {
            r = m;
        }
    }
    auto [res, ans] = solve(a, n, r);
    cout << ans + res * r;
}
