// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <iomanip>
#define dibs reserve
#define OVER9000 1234567890
#define patkan 9
#define tisic 47
#define soclose 10e-7
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define chocolate win
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):(x))
// mylittlepony
using namespace std;
	
int main() {
    cin.sync_with_stdio(0);
    int N,K;
    cin >> N >> K;
    vector< pair<int,int> > A(N);
    for(int i =0; i < N; i++) {
    	cin >> A[i].ff;
    	A[i].ss =i+1;}
    sort(A.begin(),A.end());
    set<int> X;
    multiset<long long> S;
    X.insert(0);
    X.insert(N+1);
    long long ans =0;
    for(int i =0; i < N; i++) {
    	int a =*(--X.lower_bound(A[i].ss)), b =*X.upper_bound(A[i].ss);
    	X.insert(A[i].ss);
    	S.insert(1LL*(b-a)*1LL*(A[i].ss-a)*(b-A[i].ss)/2);
    	ans +=1LL*A[i].ff*1LL*(b-a)*1LL*(A[i].ss-a)*(b-A[i].ss)/2;}
    while(K > 0) {
    	ans +=*S.rbegin();
    	S.erase(--S.end());
    	K--;}
    cout << ans << "\n";
   	return 0;}
        
// look at my code
// my code is amazing