#include <iostream>
#include <vector>
#include <deque>
#define int long long
using namespace std;
struct ln
{
int m;
int c;
int num;
ln(int _m, int _c, int _nm) : m(_m), c(_c), num(_nm) {}
friend double presek(const ln l1, const ln l2) { return (double)(l2.c - l1.c) / (double)(l1.m - l2.m); }
int operator()(int x) { return m*x + c; };
};
int km[100005];
int32_t par[205][100005];
vector<int> dp(100005);
vector<int> ndp(100005);
deque<ln> dq;
int32_t main()
{
cin.tie(NULL);
cout.tie(0);
ios_base::sync_with_stdio(false);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> km[i];
km[i] += km[i-1];
}
for (int i = 1; i <= k+1; i++)
{
dq.clear();
for (int j = 1; j <= n; j++)
{
ln tr(km[j-1], dp[j-1]-km[n]*km[j-1], j-1);
while (dq.size() >= 2 && presek(tr, dq[dq.size()-1]) <= presek(dq[dq.size()-2], tr))
dq.pop_back();
dq.push_back(tr);
while (dq.size() >= 2 && dq[0](km[j]) <= dq[1](km[j]))
dq.pop_front();
ndp[j] = dq[0](km[j]) + km[j]*km[n]-km[j]*km[j];
par[i][j] = dq[0].num;
}
dp = ndp;
}
cout << dp[n] << '\n';
int32_t tr = n;
for (int i = k+1; i > 1; i--)
{
tr = par[i][tr];
cout << tr << " ";
}
cout << "\n";
return 0;
}
