#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2 , K = 2e2 + 2;
int n , k , from[N][K] , a[N] , p[N];
long long dp[N][2] , A[N];
inline long long Add(int i , int id)
{
return A[id] + 1LL * p[i] * p[id];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i = 1 ; i <= n ; i++)
cin >> a[i];
k++;
for(int i = 1 ; i <= n ; i++)
p[i] = p[i - 1] + a[i];
for(int j = 2 ; j <= k ; j++)
{
int now = (j & 1) , prv = now ^ 1;
deque <pair<int , int>> dq;
dp[j - 1][now] = 0;
A[j - 1] = -1LL * p[j - 1] * p[j - 1] + dp[j - 1][prv];
dq.push_back({j , j - 1});
for(int i = j ; i <= n ; i++)
{
auto noww = dq.front();
int id = noww.second;
dp[i][now] = Add(i , id);
//cout << i << " : " << j << " : " << dp[i][now] << endl;
from[i][j] = id;
A[i] = dp[i][prv] - 1LL * p[i] * p[i];
if(i == n)
break;
dq.pop_front();
if(dq.empty() || dq.front().first > noww.first + 1)
dq.push_front(make_pair(noww.first + 1 , noww.second));
int las = n + 1;
while(!dq.empty())
{
//cout << "RANGOOL" << endl;
noww = dq.back();
if(Add(noww.first , i) >= Add(noww.first , noww.second))
{
dq.pop_back();
las = noww.first;
continue;
}
id = noww.second;
//cout << p[i] - p[id] << endl;
long long tmp = 1LL * (A[id] - A[i] + p[i] - p[id]) / (p[i] - p[id]);
//cout << "SALAM" << endl;
int low = noww.first , high = las;
while(high - low > 1)
{
int mid = (low + high) >> 1;
if(p[mid] >= tmp)
high = mid;
else
low = mid;
}
las = high;
break;
}
//cout << i << " " << las << endl;
if(las != n + 1)
dq.push_back({las , i});
}
}
cout << dp[n][(k & 1)] << endl;
vector <int> all;
while(k > 1)
{
all.push_back(from[n][k]);
k--;
n = all.back();
}
reverse(all.begin() , all.end());
for(auto u : all)
cout << u << " ";
cout << endl;
return 0;
}
