#include <bits/stdc++.h> #define endl "\n" using namespace std; const int MAXN = 3e5+5; long long n,k; long long a[MAXN]; void read() { cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; } long long dp[MAXN][2]; long long cnt[MAXN][2]; long long check(long long c, bool add) { for(int i = 0; i <= n; i++) dp[i][0] = dp[i][1] = cnt[i][0] = cnt[i][1] = 0; dp[0][1] = -c; cnt[0][1] = 1; for(int i = 1; i <= n; i++) { if(dp[i-1][0] > dp[i-1][1]) { dp[i][0] = dp[i-1][0]; cnt[i][0] = cnt[i-1][0]; } else if(dp[i-1][0]<dp[i-1][1]) { dp[i][0] = dp[i-1][1]; cnt[i][0] = cnt[i-1][1]; //if(dp[i-1][0] == dp[i-1][1]) cnt[i][0] = max(cnt[i-1][1],cnt[i-1][0]); } else { dp[i][0]=dp[i-1][1]; cnt[i][0]=max(cnt[i-1][0],cnt[i-1][1]); } if(dp[i-1][0] - c> dp[i-1][1]) { dp[i][1] = dp[i-1][0] - c + a[i]; cnt[i][1] = cnt[i-1][0] + 1; } else { dp[i][1] = dp[i-1][1] + a[i]; cnt[i][1] = cnt[i-1][1]; //if(dp[i-1][0] - c == dp[i-1][1]) cnt[i][1] = max(cnt[i-1][0] + 1, cnt[i-1][1]); } if(dp[i-1][0]-c==dp[i-1][1]) cnt[i][1]=max(cnt[i-1][1],cnt[i-1][0]); } /*cout << "THE C " << c << endl; for(int i = 1; i <= n; i++) { cout << " { " << dp[i][0] << " - " << dp[i][1] << " } "; } cout << endl; cout << "CNTs" << endl; for(int i = 1; i <= n; i++) { cout << " { " << cnt[i][0] << " - " << dp[i][1] << " } "; } cout << endl;*/ int b = 1; if(dp[n][0] > dp[n][1]/* || (dp[n][0] == dp[n][1] && cnt[n][0] > cnt[n][1])*/) b = 0; //cout << "the final = " << dp[n][b] + c*k << " + the cntnb " << cnt[n][b] << " thek " << k << endl; if(add) return dp[n][b] + c*k; return (bool)(cnt[n][b] >= k); } void solve() { long long l = 0, r = 1e15; long long mid; while(l <= r) { mid = (l+r)/2; bool what = check(mid,0); if(what) l = mid+1;///absolutno taka e else r = mid-1; //cout << "after: " << what << " " << l << " " << r << endl ; //cout << endl; } //cout << r << endl; if(r==-1)r=0; cout << check(r,1) << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); read(); solve(); return 0; }