#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)x.size()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(k) (1LL << (k))
#define fi first
#define se second
#define v1 vector<unsigned int>
#define v2 vector<v1>
#define INF (int)(1e9)
#define lim (int)(1000000)
#define MAX (int)(100003)
#define MAX_K (int)(203)
#define MOD (ll)(1000000007)
template <class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template <class T1, class T2>
void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}
template <class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}
using namespace std;
int N, K;
int a[MAX], trace[MAX][MAX_K];
ll pre[MAX], f[2][MAX];
ll w(int l, int r, ll f[])
{
return f[l-1] + pre[l-1] * (pre[r] - pre[l-1]);
}
struct Info
{
int p, l, r;
};
void Solve(int k, ll g[], ll f[])
{
deque<Info> st;
st.push_back({1, 1, N});
for(int i=1; i<=N; i++){
f[i] = w(st.front().p, i, g);
trace[i][k] = st.front().p - 1;
if(i == N) break;
if(st.front().r == i) st.pop_front();
else st.front().l++;
while(!st.empty() && w(i + 1, st.back().l, g) >= w(st.back().p, st.back().l, g)) st.pop_back();
if(st.empty()) st.push_back({i + 1, i + 1, N});
else {
int l = st.back().l, r = st.back().r, id;
while(l <= r){
int m = (l + r) >> 1;
if(w(i + 1, m, g) < w(st.back().p, m, g)){
id = m;
l = m + 1;
} else r = m - 1;
}
st.back().r = id;
if(id < N) st.push_back({i + 1, id + 1, N});
}
}
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// freopen("sequence.in", "r", stdin);
// freopen("sequence.out", "w", stdout);
cin >> N >> K;
for(int i=1; i<=N; i++){
cin >> a[i];
pre[i] = pre[i-1] + 1ll * a[i];
}
K++;
memset(f, -0x3f, sizeof f);
f[0][0] = 0;
for(int i=1; i<=K; i++){
Solve(i, f[!(i & 1)], f[i & 1]);
}
cout << f[K & 1][N] << '\n';
stack<int> ans;
int u = N;
for(int i=K; i>1; i--){
u = trace[u][i];
ans.push(u);
}
while(!ans.empty()){
cout << ans.top() << ' ';
ans.pop();
}
return 0;
}
