#include <bits/stdc++.h>
using namespace std;
long long dp[2][100005], a[100005];
int dq[100005], trace[205][100005];
stack<long long> st;
bool better(long long id, long long x, long long y, long long z) {return a[x]*z+dp[id][x]<=a[y]*z+dp[id][y];}
bool better2(long long id, long long x, long long y, long long z) {return (dp[id][x]-dp[id][z])*(a[z]-a[y])<=(dp[id][y]-dp[id][z])*(a[z]-a[x]);}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
long long n, k, i, j, l, r;
cin >> n >> k;
for (i=1; i<=n; i++)
{
cin >> a[i];
a[i]+=a[i-1];
};
for (i=1; i<=k+1; i++)
{
l=r=1;
dq[l]=0;
for (j=1; j<=n; j++)
{
while (l<r && better(1-i%2, dq[l], dq[l+1], a[j]-a[n])) {l++;};
dp[i%2][j]=a[dq[l]]*(a[j]-a[n])+dp[1-i%2][dq[l]]+a[n]*a[j]-a[j]*a[j];
trace[i][j]=dq[l];
while (r>l && better2(1-i%2, j, dq[r], dq[r-1])) {r--;};
dq[++r]=j;
};
};
cout << dp[(k+1)%2][n] << "\n";
i=k+1; j=n;
while (i>1)
{
st.push(trace[i][j]);
j=trace[i][j]; i--;
};
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
};
}
