#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+10;
const int MAXK = 210;
int split[MAXK][MAXN];
ll arr[MAXN], pref[MAXN], dp[2][MAXN], Q[MAXN];
int N;
bool check1(int x, int y, int j){
return (dp[0][y]-dp[0][x] >= (pref[y]-pref[x])*(pref[N]-pref[j]));
}
bool check2(int x, int y, int j){
return ((dp[0][y]-dp[0][x])*(pref[j]-pref[y]) <= (dp[0][j]-dp[0][y])*(pref[y]-pref[x]));
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int K; cin >> N >> K;
fill(dp[0],dp[0]+N+1,0);
for(int i = 1;i<=N;++i){
cin >> arr[i];
pref[i] = pref[i-1]+arr[i]; //pref[i] includes arr[i]
}
int l = 1, r = 1;
for(int i = 1;i<=K;++i){
Q[r] = 0; ++r;
for(int j = 1;j<=N;++j){
while(r-l > 1 && check1(Q[l],Q[l+1],j)){
++l;
}
dp[1][j] = dp[0][Q[l]]+(pref[j]-pref[Q[l]])*(pref[N]-pref[j]);
split[i][j] = Q[l];
while(r-l > 1 && check2(Q[r-2],Q[r-1],j)){
--r;
}
Q[r] = j; ++r;
}
l = r = 1;
for(int j = 1;j<=N;++j){
dp[0][j] = dp[1][j];
}
}
ll ans = -1; int pos = -1;
for(int i = 1;i<=N;++i){
if(dp[0][i] > ans){
ans = dp[0][i];
pos = i;
}
}
cout << ans << "\n";
for(int i = 0;i<K;++i){
cout << pos << " ";
pos = split[K-i][pos];
}
cout << "\n";
return 0;
}
