#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
struct line{
ll m, c, id;
ll eval(ll x){return m * x + c;}
ld inter(line l){return (long double)(c - l.c) / (l.m - m);}
};
int n, k;
ll a[100005], dp[100005][2], pre[100005];
int race[100005][202];
deque<ll> dq;
bool bad(__int128_t m1, __int128_t b1, __int128_t m2, __int128_t b2, __int128_t m3, __int128_t b3){
return (b2 - b1) * (m1 - m3) >= (m1 - m2) * (b3 - b1);
}
int main(){
// freopen("task.inp","r",stdin);
// freopen("task.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n ; ++i){
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
for(int i = 1 ; i <= n ; ++i)
dp[i][0] = pre[i] * (pre[n] - pre[i]);
for(int i = 1; i <= k ; ++i){
dq.clear();
for(int j = i + 1 ; j <= n ; ++j){
ll suf = pre[n] - pre[j];
while((int)dq.size() >= 2){
ll s1 = dq.back(), s2 = dq[dq.size() - 2];
if(bad(-pre[s1],dp[s1][0],-pre[s2],dp[s2][0],-pre[j - 1],dp[j - 1][0]))
dq.pop_back();
else break;
}
dq.push_back(j - 1);
while((int)dq.size() >= 2){
ll s1 = dq[0];
ll s2 = dq[1];
s1 = dp[s1][0] + (pre[j] - pre[s1]) * suf;
s2 = dp[s2][0] + (pre[j] - pre[s2]) * suf;
if(s1 <= s2) dq.pop_front();
else break;
}
ll val = dp[dq[0]][0] + (pre[j] - pre[dq[0]]) * suf;
dp[j][1] = val;
race[j][i] = dq[0];
}
for(int j = i + 1 ; j <= n ; ++j)
dp[j][0] = dp[j][1];
}
ll res = dp[n][1];
vector<int> v;
int pos = n;
for(int i = k ; i >= 1; --i){
pos = race[pos][i];
v.push_back(pos);
}
reverse(v.begin(),v.end());
cout << res << '\n';
for(int i : v) cout << i << ' ';
return 0;
}
