#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[1000005], race[100005][205];
deque<ll> dq;
bool bad(ll m1, ll b1, ll m2, ll b2, ll m3, ll b3){
return (m2 - b2) * (m1 - b1) >= (m3 - b3) * (m2 - b2);
}
int main(){
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;
}
