#include <bits/stdc++.h>
using namespace std;
int main()
{
long long N, K;
cin >> N >> K;
vector<long long> Tab(N), cum(N + 1);
for (long long i = 0; i < N; i++)
{
cin >> Tab[i];
cum[i + 1] = cum[i] + Tab[i];
}
vector<long long> dp(N);
vector<vector<int>> dp2(K, vector<int>(N));
deque<vector<long long>> CHT, CHT2;
CHT.push_back({0, 0, 0});
for (long long i = 0; i < K; i++)
{
CHT2 = {{0, 0, 0}};
for (long long j = 0; j < N; j++)
{
while (CHT.size() > 1)
{
long long m = (CHT[1][0] - CHT[0][0]) / (CHT[1][1] - CHT[0][1]);
if (cum[N] - cum[j + 1] <= m)
CHT.pop_front();
else
break;
}
dp[j] = cum[j + 1] * (cum[N] - cum[j + 1]) + CHT.front()[0] - CHT.front()[1] * (cum[N] - cum[j + 1]);
dp2[i][j] = CHT.front()[2];
while (CHT2.size() > 1)
{
if (CHT2[CHT2.size() - 2][1] == CHT2[CHT2.size() - 1][1] || (double)((dp[j] - CHT2[CHT2.size() - 2][0]) / (cum[j + 1] - CHT2[CHT2.size() - 2][1])) > (double)((CHT2.back()[0] - CHT2[CHT2.size() - 2][0]) / (CHT2.back()[1] - CHT2[CHT2.size() - 2][1])))
CHT2.pop_back();
else
break;
}
if (CHT2.back()[0] < dp[j])
CHT2.push_back({dp[j], cum[j + 1], j});
}
swap(CHT, CHT2);
}
long long best = 0, best2 = 0;
for (long long i = 0; i < N; i++)
{
if (best < dp[i])
{
best = dp[i];
best2 = i;
}
}
cout << best << '\n';
vector<int> occ(N);
int buff = 0;
for (int i = K - 1; i >= 0; i--)
{
cout << ((occ[best2]) ? (buff + 1) : (best2 + 1)) << ' ';
occ[(occ[best2]) ? buff : best2] = 1;
while (occ[buff])
buff++;
best2 = dp2[i][best2];
}
}
