#include <iostream>
#include <deque>
using namespace std;
#define int long long
const int MAX_NB = 1e5 + 1;
const int MAX_COUPE = 200 + 1;
struct Info
{
int pos, val, deb, fin;
};
int nbInt, nbCoupe;
int valeurs[MAX_NB];
int cumul[MAX_NB];
int dp[2][MAX_COUPE];
int origine[MAX_NB][MAX_COUPE];
deque<Info> enCours[MAX_COUPE];
int find_Coupe(int pos1, int val1, int pos2, int val2)
{
int deb = pos2, fin = nbInt;
while(deb < fin - 1)
{
int mid = (deb + fin) / 2;
if(val1 + (cumul[mid] - cumul[pos1]) * (cumul[nbInt] - cumul[mid]) < val2 + (cumul[mid] - cumul[pos2]) * (cumul[nbInt] - cumul[mid]))
{
fin = mid;
}
else
{
deb = mid;
}
}
if(val1 + (cumul[deb] - cumul[pos1]) * (cumul[nbInt] - cumul[deb]) < val2 + (cumul[deb] - cumul[pos2]) * (cumul[nbInt] - cumul[deb]))
{
return deb;
}
return fin;
}
void ajoute(int pos, int coupe, int val)
{
while(!enCours[coupe].empty())
{
int ces = find_Coupe(enCours[coupe].back().pos, enCours[coupe].back().val, pos, val);
if(ces - 1 < enCours[coupe].back().deb)
{
enCours[coupe].pop_back();
}
else
{
enCours[coupe].back().fin = ces - 1;
break;
}
}
if(enCours[coupe].empty())
{
enCours[coupe].push_back({pos, val, 0, nbInt});
}
else
{
enCours[coupe].push_back({pos, val, enCours[coupe].back().fin + 1, nbInt});
}
}
int32_t main()
{
ios::sync_with_stdio(false);
cin >> nbInt >> nbCoupe;
for(int iNb = 1; iNb <= nbInt; iNb++)
{
cin >> valeurs[iNb];
cumul[iNb] += valeurs[iNb];
cumul[iNb] += cumul[iNb - 1];
}
enCours[0].push_back({0, 0, 0, nbInt});
int result = 0;
int dep = 0;
for(int iPos = 1; iPos <= nbInt; iPos++)
{
for(int iCoupe = nbCoupe; iCoupe >= 1; iCoupe--)
{
if(enCours[iCoupe - 1].empty())
{
continue;
}
while(enCours[iCoupe - 1].front().fin < iPos)
{
enCours[iCoupe - 1].pop_front();
}
int pos = enCours[iCoupe - 1].front().pos, val = enCours[iCoupe - 1].front().val;
dp[iPos % 2][iCoupe] = val + (cumul[iPos] - cumul[pos]) * (cumul[nbInt] - cumul[iPos]);
origine[iPos][iCoupe] = pos;
ajoute(iPos, iCoupe, dp[iPos % 2][iCoupe]);
}
if(dp[iPos % 2][nbCoupe] > result)
{
result = dp[iPos % 2][nbCoupe];
dep = iPos;
}
}
cout << result << endl;
int posCoupe = nbCoupe;
while(posCoupe > 0)
{
cout << dep << " ";
dep = origine[dep][posCoupe];
posCoupe--;
}
cout << endl;
}
