#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = (ll)1e9+7;
#define P pair
#define S second
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
void file() {
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}
struct li_chao {
private:
struct line {
ll m,p;
ll evaluate(ll x) {
return m*x+p;
}
line(ll _m=0,ll _p=-1e18):m(_m),p(_p){}
};
struct node {
line l;
int id;
node *left=nullptr;
node *right=nullptr;
node(line _l=line(),int _id=-1):l(_l),left(nullptr),right(nullptr),id(_id){}
};
node neutral={line(),-1};
public:
node *root=nullptr;
ll x_min,x_max;
void init(ll a,ll b) {
x_min=a,x_max=b;
}
void insert(line x,int id,ll lx,ll rx,node *&nd) {
if (!nd) {
nd=new node(x,id);
return;
}
ll m=(lx+rx)/2;
bool m_b=x.evaluate(m)>nd->l.evaluate(m);
bool l_b=x.evaluate(lx)>nd->l.evaluate(lx);
if (m_b) {
swap(x,nd->l);
swap(id,nd->id);
}
if (rx-lx==0) {
return;
}
if (l_b!=m_b) {
insert(x,id,lx,m,nd->left);
}
else
insert(x,id,m+1,rx,nd->right);
}
void insert(ll m,ll p,int id) {
insert(line(m,p),id,x_min,x_max,root);
}
node calc(ll x,ll lx,ll rx,node *nd) {
if (!nd) {
return node();
}
ll val=nd->l.evaluate(x);
if (rx-lx==0) {
return {nd->l,nd->id};
}
ll m=(lx+rx)/2;
if (x<=m) {
node a=calc(x,lx,m,nd->left);
if (val>a.l.evaluate(x)) {
return {nd->l,nd->id};
}
else {
return a;
}
}
else {
node b=calc(x,m+1,rx,nd->right);
if (val>b.l.evaluate(x)) {
return {nd->l,nd->id};
}
else {
return b;
}
}
}
int calc(ll x) {
return calc(x,x_min,x_max,root).id;
}
};
void solve() {
int n,k;
cin>>n>>k;
k++;
int a[n+1];
for (int i=1;i<=n;i++) {
cin>>a[i];
}
ll dp[n+1][k+1];
int best[n+1][k+1];
dp[0][0]=0LL;
li_chao tree[k+1];
for (int i=0;i<=k;i++) {
tree[i].init(0,1e9);
}
ll pref[n+1];
pref[0]=0LL;
for (int i=1;i<=n;i++) {
pref[i]=pref[i-1]+a[i];
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=k;j++) {
if (j==1) {
dp[i][1]=0;
best[i][1]=0;
}
else {
int g=tree[j-1].calc(pref[i]);
best[i][j]=g;
if (g!=-1) {
dp[i][j]=dp[g][j-1]+(pref[i]-pref[g])*pref[g];
}
}
}
for (int j=1;j<=k;j++) {
if (best[i][j]!=-1) {
tree[j].insert(pref[i],dp[i][j]-pref[i]*pref[i],i);
}
}
}
cout<<dp[n][k]<<endl;
int cur=n;
V<int>vp;
for (int i=k;i>=2;i--) {
vp.pb(best[cur][i]);
cur=best[cur][i];
}
reverse(all(vp));
for (auto u:vp) {
cout<<u<<" ";
}
cout<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
//file();
solve();
return 0;
}
