#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll,ll> pi;
typedef tuple<int,int,int> ti;
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int N = 100001;
int n,k;
int a[N],s[N],par[201][N],tmp[N];
ll dp[2][N];
struct CHT {
deque<pi> dq;
deque<int> idx;
ll f(pi line, ll x) {
return line.first*x + line.second;
}
pi query(ll x) {
while(dq.size()>1) {
if(f(dq[0],x)<f(dq[1],x)) {
dq.pop_front();
idx.pop_front();
} else {
break;
}
}
return {f(dq[0],x), idx[0]};
}
double intersect(ll m1, ll c1, ll m2, ll c2) {
return (double) (c2-c1)/(m1-m2);
}
double intersect(pi a, pi b) {
return intersect(a.first,a.second,b.first,b.second);
}
void insert(ll m, ll c, int id) {
pi line = {m,c};
while(dq.size() > 1) {
int s = dq.size();
if(intersect(dq[s-1],line) <= intersect(dq[s-2],line)) {
dq.pop_back();
idx.pop_back();
} else {
break;
}
}
dq.push_back(line);
idx.push_back(id);
}
void clear() {
while (dq.size()) dq.pop_front();
while (idx.size()) idx.pop_front();
}
} ch;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin.exceptions(ios::badbit|ios::failbit);
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = n; i >= 1; --i) s[i]=s[i+1]+a[i];
for (int j = 1; j <= k; ++j) {
int f=j%2;
for (int i = n; i > 1; --i) {
if (j>n-i+1) continue;
ch.insert(s[i],(ll)dp[!f][i]-(ll)s[i]*(ll)s[i],i);
dp[f][i-1]=ch.query(s[i-1]).first;
tmp[i-1]=ch.query(s[i-1]).second;
}
for (int i = n; i >= 1; --i) {
dp[!f][i]=dp[f][i];
par[j][i]=tmp[i];
}
ch.clear();
}
cout << dp[0][1] << '\n';
int ptr = 1;
while (ptr) {
ptr = par[k--][ptr];
if (ptr) cout << ptr-1 << ' ';
}
return 0;
}
