#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int N=1e5+5;
const int K=202;
int n, k;
ll dp[2][N];
int bac[N][K];
ll pref[N];
ll dp2[20][20];
int ind, koji[N];
vector <pll> v;
int ccw(pll a, pll b, pll c) {
ll ret=a.X*(b.Y-c.Y)+b.X*(c.Y-a.Y)+c.X*(a.Y-b.Y);
if (ret>0) return 1;
if (ret<0) return -1;
return 0;
}
ll f(pll pp, ll x) {
return pp.X*x+pp.Y;
}
void dodaj(pll pp, int br) {
while (v.size()>1 && ccw(v[(int)v.size()-2], v.back(), pp)>=0) v.pop_back();
koji[v.size()]=br;
v.pb(pp);
}
pli query(ll x) {
ind=min(ind, (int)v.size()-1);
while (ind+1<(int)v.size() && f(v[ind], x)<=f(v[ind+1], x)) ++ind;
return mp(f(v[ind], x), koji[ind]);
}
void backtrack() {
pii pp=mp(n, k);
while (pp.Y) {
pp.X=bac[pp.X][pp.Y--];
printf("%d ", pp.X);
}
}
void solve() {
int b=1;
for (int j=1; j<=k; ++j) {
v.clear();
ind=0;
for (int i=1; i<=j; ++i) dodaj(mp(pref[i], dp[!b][i]-pref[i]*pref[i]), i);
for (int i=j+1; i<=n; ++i) {
pli curr=query(pref[i]);
bac[i][j]=curr.Y;
dp[b][i]=curr.X;
dodaj(mp(pref[i], dp[!b][i]-pref[i]*pref[i]), i);
}
b^=1;
}
printf("%lld\n", dp[!b][n]);
}
void brut() {
fill(dp2[0], dp2[0]+20, -MAX);
dp2[0][0]=0;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=k; ++j) {
for (int l=0; l<i; ++l) {
ll curr=dp2[l][j-1]+pref[l]*(pref[i]-pref[l]);
if (curr>=dp2[i][j]) dp2[i][j]=curr, bac[i][j]=l;
}
}
}
printf("%lld\n", dp2[n][k]);
}
void load() {
scanf("%d %d", &n, &k);
for (int i=1; i<=n; ++i) {
scanf("%lld", &pref[i]);
pref[i]+=pref[i-1];
}
}
int main() {
load();
if (n<=10) brut();
else solve();
backtrack();
return 0;
}
