#include <iostream>
#include <deque>
using namespace std;
typedef long long llong;
const int MAXN = 1e5 + 10;
const int MAXK = 2e2 + 10;
struct Line
{
llong k, m, idx;
Line(){};
Line(llong k, llong m, llong idx)
{
this->k = k;
this->m = m;
this->idx = idx;
}
long double intersect(Line &other)
{
return (long double)(m - other.m) / (long double)(other.k - k);
}
llong eval(llong x)
{
return k * x + m;
}
};
struct CHT
{
deque < Line > dq;
CHT(){};
void addLine(Line l)
{
if(!dq.empty() && l.k == dq.back().k)
{
if(l.m < dq.back().m)
return;
dq.pop_back();
}
while(dq.size() >= 2 && dq[dq.size() - 1].intersect(dq[dq.size() - 2]) >= dq[dq.size() - 1].intersect(l))
{
dq.pop_back();
}
dq.push_back(l);
}
void addLine(llong k, llong m, llong idx)
{
addLine(Line(k, m, idx));
}
pair < llong, int > query(llong x)
{
while(dq.size() >= 2 && dq[0].intersect(dq[1]) <= x)
{
dq.pop_front();
}
return {dq[0].eval(x), dq[0].idx};
}
void clean()
{
dq.clear();
}
};
CHT cht;
int n, k;
int a[MAXN];
llong pref[MAXN];
llong dp[MAXN][2];
int from[MAXN][MAXK];
void read()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
}
void precomp()
{
for(int i = 1; i <= n; i++)
{
pref[i] = pref[i - 1] + a[i];
}
}
void solve()
{
for(int j = 1; j <= k + 1; j++)
{
cht.clean();
cht.addLine(0, 0, 0);
for(int i = 1; i <= n; i++)
{
pair < llong, int > p = cht.query(pref[i]);
dp[i][j & 1] = pref[i] * pref[n] - pref[i] * pref[i] + p.first;
from[i][j] = p.second;
cht.addLine(pref[i], dp[i][(j - 1) & 1] - pref[i] * pref[n], i);
}
}
llong ans = dp[n][(k + 1) & 1];
int idx = from[n][k + 1];
cout << ans << endl;
for(int j = k; j >= 1; j--)
{
cout << idx << " ";
idx = from[idx][j];
}
cout << endl;
}
int main()
{
read();
precomp();
solve();
return 0;
}
