#include <bits/stdc++.h> #define int long long using namespace std; const int maxn=1e6+1; int inf=LLONG_MAX; int n,k; int a[maxn]; int dp[maxn][2]; int cnt[2]; int ch; int ma; void read() { cin>>n>>k; for(int i=1;i<=n;i++) { cin>>a[i]; if(a[i]>0) { ma+=a[i]; } } } void prec() { dp[0][0]=-inf; for(int i=1;i<=n;i++) { dp[i][0]=max(dp[i-1][0], dp[i-1][1]); dp[i][1]=max(dp[i-1][0], dp[i-1][1])+a[i]; } ch=max(dp[n][0], dp[n][1]); } bool check(int c) { ch=max(dp[n][0], dp[n][1]); memset(dp, 0, sizeof(dp)); for(int i=1;i<=n;i++) { dp[i][0]= max(dp[i-1][0], dp[i-1][1]); dp[1][1]=max(dp[i-1][1], dp[i-1][0]+c)+a[i]; } return (max(dp[n][0], dp[n][1])>=ch); } void bs() { int l=0, r=ma,mid; while(r-l>1) { mid=(l+r)/2; if(check(mid)) { r=mid; } else { l=mid; } } cout<<l<<endl; } signed main() { ios_base::sync_with_stdio(false); read(); prec(); bs(); return 0; }