#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int64_t INF=2e18;
const int MAXN=1e5+10;
const int MAXK=2e2+5;
struct Prava {
int64_t a;
int64_t b;
int64_t x;
int ind;
};
vector <Prava> env[MAXK];
stack <int> st;
int br[MAXK];
int64_t a[MAXN], pref[MAXN];
int ind[MAXN][MAXK];
bool check (int64_t a1, int64_t b1, int64_t a2, int64_t b2, int64_t a3, int64_t b3) {
return (a1-a2)*(b3-b1)<=(a1-a3)*(b2-b1);
}
int64_t find_intersection(int64_t a1, int64_t b1, int64_t a2, int64_t b2) {
int64_t da, db;
da=a1-a2; db=b2-b1;
if (da==0) return INF;
return (db+da-1)/da;
}
void add(int k, int64_t a, int64_t b, int ind) {
if (env[k].empty()) {
env[k].push_back({a,b,-INF,ind});
return;
}
int64_t 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];
}
/*int64_t 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;
int64_t s, ans;
for (int i=1;i<=n;i++) {
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;
s=env[j-1][br[j-1]].a*pref[i]+env[j-1][br[j-1]].b;
if (i==n && j==k+1) ans=s;
add(j,-pref[i],s+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;
}
cout << -ans << 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;
}
