#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef pair<ll,int32_t> pint;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(int32_t i=s;i<=int32_t(e);++i)
#define DEC(i,s,e) for(int32_t i=s;i>=int32_t(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define maxk 201
#define maxn 100001
#define int ll
typedef pair <pi,int32_t> pii;
typedef long double ld;
int32_t N,K,A[maxn];
ll ss[maxn];
deque <pii> dq;
int32_t pre[maxn][maxk];
inline int readInt() {
int x = 0;
char ch = getchar_unlocked();
while (ch < '0' || ch > '9') ch = getchar_unlocked();
while (ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar_unlocked();
}
return x;
}
static inline int f(pi line, int32_t i){
return line.f * i + line.s;
}
static inline pint query(int x,int32_t i){
while (dq.size() > 1){
if (dq[1].s > i) break;
if (f(dq[0].f,x) < f(dq[1].f,x)){
dq.pop_front();
}else break;
}
return pint(f(dq[0].f,x),dq[0].s);
}
static inline ld intersect(pi line1,pi line2){
return ld(line1.s - line2.s) / ld(line2.f - line1.f);
}
static inline void insert(pi line,int32_t i){
while (dq.size() > 1){
if (intersect(dq.back().f,line) <= intersect(dq[dq.size() - 2].f,line)){
dq.pop_back();
}else break;
}
dq.pb(pii(line,i));
}
int32_t main(){
fast;
N = readInt(); K = readInt();
FOR(i,1,N) A[i] =readInt(),ss[i] = ss[i-1] + A[i];
vector <pii> cur;
FOR(j,0,K){
FOR(i,j+1,N){
int res;
if (i == 1) res = 0;
else if (j == 0) res = 0;
else{
pint a = query(ss[i],i);
res = a.f;
pre[i][j] = a.s;
}
if (i == N && j == K) cout<<res<<'\n';
cur.pb(pii(pi(ss[i],res - ss[i] * ss[i]),i));
//cout<<dp[i][j]<<' ';
}
dq.clear();
aFOR(k,cur) insert(k.f,k.s);
cur.clear();
//while (!cur.empty()) insert(cur.back().f,cur.back().s),cur.pop_back();
//cout<<'\n';
}
int32_t cr = pre[N][K];
cout<<cr<<' ';
DEC(i,K-1,1){
cout<<pre[cr][i]<<' ';
cr = pre[cr][i];
}
}
