// 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

Ly8gaW9zdHJlYW0gaXMgdG9vIG1haW5zdHJlYW0KI2luY2x1ZGUgPGNzdGRpbz4KLy8gYml0Y2ggcGxlYXNlCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxpb21hbmlwPgojZGVmaW5lIGRpYnMgcmVzZXJ2ZQojZGVmaW5lIE9WRVI5MDAwIDEyMzQ1Njc4OTAKI2RlZmluZSBwYXRrYW4gOQojZGVmaW5lIHRpc2ljIDQ3CiNkZWZpbmUgc29jbG9zZSAxMGUtNwojZGVmaW5lIEFMTF9USEUoQ0FLRSxMSUUpIGZvcihhdXRvIExJRSA9Q0FLRS5iZWdpbigpOyBMSUUgIT0gQ0FLRS5lbmQoKTsgTElFKyspCiNkZWZpbmUgY2hvY29sYXRlIHdpbgojZGVmaW5lIGZmIGZpcnN0CiNkZWZpbmUgc3Mgc2Vjb25kCiNkZWZpbmUgYWJzKHgpICgoeCA8IDApPy0oeCk6KHgpKQovLyBteWxpdHRsZXBvbnkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCQppbnQgbWFpbigpIHsKICAgIGNpbi5zeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBpbnQgTixLOwogICAgY2luID4+IE4gPj4gSzsKICAgIHZlY3RvcjwgcGFpcjxpbnQsaW50PiA+IEEoTik7CiAgICBmb3IoaW50IGkgPTA7IGkgPCBOOyBpKyspIHsKICAgIAljaW4gPj4gQVtpXS5mZjsKICAgIAlBW2ldLnNzID1pKzE7fQogICAgc29ydChBLmJlZ2luKCksQS5lbmQoKSk7CiAgICBzZXQ8aW50PiBYOwogICAgbXVsdGlzZXQ8bG9uZyBsb25nPiBTOwogICAgWC5pbnNlcnQoMCk7CiAgICBYLmluc2VydChOKzEpOwogICAgbG9uZyBsb25nIGFucyA9MDsKICAgIGZvcihpbnQgaSA9MDsgaSA8IE47IGkrKykgewogICAgCWludCBhID0qKC0tWC5sb3dlcl9ib3VuZChBW2ldLnNzKSksIGIgPSpYLnVwcGVyX2JvdW5kKEFbaV0uc3MpOwogICAgCVguaW5zZXJ0KEFbaV0uc3MpOwogICAgCVMuaW5zZXJ0KDFMTCooYi1hKSoxTEwqKEFbaV0uc3MtYSkqKGItQVtpXS5zcykvMik7CiAgICAJYW5zICs9MUxMKkFbaV0uZmYqMUxMKihiLWEpKjFMTCooQVtpXS5zcy1hKSooYi1BW2ldLnNzKS8yO30KICAgIHdoaWxlKEsgPiAwKSB7CiAgICAJYW5zICs9KlMucmJlZ2luKCk7CiAgICAJUy5lcmFzZSgtLVMuZW5kKCkpOwogICAgCUstLTt9CiAgICBjb3V0IDw8IGFucyA8PCAiXG4iOwogICAJcmV0dXJuIDA7fQogICAgICAgIAovLyBsb29rIGF0IG15IGNvZGUKLy8gbXkgY29kZSBpcyBhbWF6aW5n

NCAyCjUgMSAyIDM=

4 2
5 1 2 3