#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const long long INF=2e18;
const int MAXN=1e5+10;
const int MAXK=2e2+5;
struct Prava {
long long a;
long long b;
long long x;
int ind;
};
vector <Prava> env[MAXK];
stack <int> st;
int br[MAXK];
long long a[MAXN], pref[MAXN], dp[MAXN][MAXK];
int ind[MAXN][MAXK];
bool check (long long a1, long long b1, long long a2, long long b2, long long a3, long long b3) {
return (a1-a2)*(b3-b1)<=(a1-a3)*(b2-b1);
}
long long find_intersection(long long a1, long long b1, long long a2, long long b2) {
long long da, db;
da=a1-a2; db=b2-b1;
if (da==0) return INF;
return (db+da-1)/da;
}
void add(int k, long long a, long long b, int ind) {
if (env[k].empty()) {
env[k].push_back({a,b,-INF,ind});
return;
}
long long a1, b1, a2, b2, x;
int i;
while (env[k].size()>1) {
i=env[k].size();
a1=env[k][i-2].a; b1=env[k][i-2].b;
a2=env[k][i-1].a; b2=env[k][i-1].b;
if (!check(a,b,a1,b1,a2,b2)) break;
if (i-1==br[k]) br[k]--;
env[k].pop_back();
}
i=env[k].size();
a1=env[k][i-1].a; b1=env[k][i-1].b;
x=find_intersection(a1,b1,a,b);
env[k].push_back({a,b,x,ind});
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k;
cin >> n >> k;
for (int i=1;i<=n;i++) {
cin >> a[i];
pref[i]=pref[i-1]+a[i];
}
/*long long s;
for (int i=1;i<=n;i++) {
for (int j=min(i,k+1);j>1;j--) {
dp[i][j]=-1;
for (int p=i-1;p>=j-1;p--) {
s=dp[p][j-1]+(pref[i]-pref[p])*pref[p];
if (s>dp[i][j]) {
dp[i][j]=s;
ind[i][j]=p;
}
}
}
dp[i][1]=0;
ind[i][1]=-1;
}
dp[n][k+1]=-dp[n][k+1];*/
ind[0][1]=-1;
for (int i=1;i<=n;i++) {
/*if (a[i]==0) {
for (int j=min(i,k+1);j>=1;j--) {
if (j==i) {
dp[i][j]=dp[i-1][j-1];
ind[i][j]=i-1;
add(j,-pref[i],dp[i][j]+pref[i]*pref[i],i);
continue;
}
dp[i][j]=dp[i-1][j];
ind[i][j]=ind[i-1][j];
}
continue;
}*/
for (int j=min(i,k+1);j>1;j--) {
while (br[j-1]<env[j-1].size() && env[j-1][br[j-1]].x<=pref[i]) br[j-1]++;
br[j-1]--;
ind[i][j]=env[j-1][br[j-1]].ind;
dp[i][j]=env[j-1][br[j-1]].a*pref[i]+env[j-1][br[j-1]].b;
add(j,-pref[i],dp[i][j]+pref[i]*pref[i],i);
///cout << i << ' ' << j << ' ' << dp[i][j] << endl;
}
add(1,-pref[i],pref[i]*pref[i],i);
ind[i][1]=-1;
dp[i][0]=0;
}
cout << -dp[n][k+1] << endl;
int i=ind[n][k+1], curk=k;
while (curk>=1) {
st.push(i);
i=ind[i][curk];
curk--;
}
while (!st.empty()) {
cout << st.top();
st.pop();
if (!st.empty()) cout << ' ';
}
cout << endl;
return 0;
}
