#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5, kx=205;
ll n, k, dp[2][nx], qs[nx];
int back[kx][nx];
struct line
{
ll m, c;
int idx;
line(ll m, ll c, int idx): m(m), c(c), idx(idx){}
ll val(ll x) {return m*x+c;}
};
deque<line> dq;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>k;
for (int i=1; i<=n; i++) cin>>qs[i], qs[i]+=qs[i-1];
for (int l=1; l<=k; l++)
{
dq.clear();
int cur=l%2, pv=1-cur;
for (int i=1; i<=n;i ++)
{
line nw=line(qs[i-1], dp[pv][i-1]-qs[i-1]*qs[i-1], i-1);
while (dq.size()>1&&(dq[dq.size()-2].c-dq.back().c)*(nw.m-dq[dq.size()-2].m)<=(dq[dq.size()-2].c-nw.c)*(dq.back().m-dq[dq.size()-2].m)) dq.pop_back();
dq.push_back(nw);
while (dq.size()>1&&dq[0].val(qs[i])<=dq[1].val(qs[i])) dq.pop_front();
dp[cur][i]=dq.front().val(qs[i]);
back[l][i]=dq.front().idx;
}
}
cout<<dp[k%2][n]<<'\n';
int tmp=n, ly=k;
while (back[ly][tmp]) cout<<(tmp=back[ly--][tmp])<<' ';
}
