#include <iostream>
#include <deque>
using namespace std;
const long long MAX_NB = 1e5 + 1;
const long long MAX_COUPE = 200 + 1;
struct Info
{
long long pos, val, deb, fin;
};
long long nbInt, nbCoupe;
long long valeurs[MAX_NB];
long long cumul[MAX_NB];
long long dp[2][MAX_COUPE];
int origine[MAX_NB][MAX_COUPE];
deque<Info> enCours[MAX_COUPE];
long long find_Coupe(long long pos1, long long val1, long long pos2, long long val2)
{
long long deb = pos2, fin = nbInt;
while(deb < fin - 1)
{
long long 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(long long pos, long long coupe, long long val)
{
while(!enCours[coupe].empty())
{
if((cumul[enCours[coupe].back().deb] - cumul[enCours[coupe].back().pos]) * (cumul[nbInt] - cumul[enCours[coupe].back().deb]) + enCours[coupe].back().val < (cumul[enCours[coupe].back().deb] - cumul[pos]) * (cumul[nbInt] - cumul[enCours[coupe].back().deb] + val))
{
enCours[coupe].pop_back();
continue;
}
long long 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(long long iNb = 1; iNb <= nbInt; iNb++)
{
cin >> valeurs[iNb];
cumul[iNb] += valeurs[iNb];
cumul[iNb] += cumul[iNb - 1];
}
if(nbInt == 2)
{
cout << 1 << endl;
cout << valeurs[1] * valeurs[2] << endl;
return 0;
}
enCours[0].push_back({0, 0, 0, nbInt});
long long result = 0;
long long dep = 0;
for(long long iPos = 1; iPos <= nbInt; iPos++)
{
for(long long iCoupe = nbCoupe; iCoupe >= 1; iCoupe--)
{
if(enCours[iCoupe - 1].empty())
{
continue;
}
while(enCours[iCoupe - 1].front().fin < iPos)
{
enCours[iCoupe - 1].pop_front();
}
long long 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;
long long posCoupe = nbCoupe;
while(posCoupe > 0)
{
cout << dep << " ";
dep = origine[dep][posCoupe];
posCoupe--;
}
cout << endl;
}
