#include <bits/stdc++.h>
using namespace std;
long long dp[100005][2], a[100005];
int back[100005][205], deq[100005];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k, cur;
cin >> n >> k;
for (int i=1; i<=n; i++)
{
long long x;
cin >> x;
a[i]=a[i-1]+x;
}
for (int i=1; i<=k+1; i++)
{
deq[0]=i-1;
int ii=i&1, iii=(i&1)^1, l=0, r=1;
for (int j=i; j<=n; j++)
{
// cout << "i j " << i << ' ' << j << '\n';
if (r-l>=2)
{
int x=deq[l], y=deq[l+1];
while (dp[y][iii]-dp[x][iii]>=(a[n]-a[j])*(a[y]-a[x]))
{
l++;
// cout << "deq pop back, now only have " << r-l << '\n';
if (r-l<2)
break;
x=deq[l];
y=deq[l+1];
}
}
dp[j][ii]=dp[deq[l]][iii]+(a[n]-a[j])*(a[j]-a[deq[l]]);
back[j][i]=deq[l];
if (r-l>=2)
{
int x=deq[r-2], y=deq[r-1];
while ((dp[y][iii]-dp[x][iii])*(a[j]-a[y])<=(dp[j][iii]-dp[y][iii])*(a[y]-a[x]))
{
r--;
// cout << "deq pop back, now only have " << r-l << '\n';
if (r-l<2)
break;
x=deq[r-2];
y=deq[r-1];
}
}
deq[r]=j;
r++;
// cout << "deq push back " << j << ", now have " << r-l << '\n';
}
}
cout << dp[n][(k+1)&1] << '\n';
cur=n;
for (int i=k+1; i>=2; i--)
{
cur=back[cur][i];
deq[i]=cur;
}
for (int i=2; i<=k+1; i++)
cout << deq[i] << ' ';
return 0;
}
