#pragma GCC optimize ("-O2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cassert>
#include <map>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
//#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define index(xs, xe, y) (int)(lower_bound(xs, xe, y) - xs)
#define _1 first
#define _2 second
#define pb push_back
#define MOD 1000000007
#define INF (1LL<<60)
typedef pair<long long, long long> P;
inline P rel(long long p, long long q) {
if (q < 0) p = -p, q = -q;
return P(p, q);
}
inline P x_intersect(P a, P b) { return rel(b._2-a._2, a._1-b._1); }
inline bool ord(P a, P b) {
// ap/aq < bp/bq
//return (__int128)a._1*b._2 < (__int128)a._2*b._1;
return a._1*b._2 < a._2*b._1;
}
struct ConvexHullTrick {
vector<pair<P, int> > ps;
int h = 0;
void add(long long x, long long y, int attr) {
if (!ps.empty() && ps.back()._1._1 == x) {
if (ps.back()._1._2 < y) return;
ps.pop_back();
}
P c = P(x, y);
while (ps.size() >= 2) {
P a = ps[ps.size()-2]._1, b = ps[ps.size()-1]._1;
if (ord(x_intersect(b, c), x_intersect(a, c)) && ord(x_intersect(a, c), x_intersect(a, b))) break;
ps.pop_back();
}
//h = max(0, min(h, (int)ps.size()-1));
ps.pb(make_pair(P(x, y), attr));
}
P f(long long a) {
if (ps.empty()) return P(-1, INF);
while (h+1 < ps.size()) {
if (ord(P(a, 1), x_intersect(ps[h]._1, ps[h+1]._1))) h++;
else break;
}
return P(ps[h]._2, a*ps[h]._1._1+ps[h]._1._2);
}
};
int N, K;
int B[100001];
int pre[100001][202];
long long dp[301][202];
signed main() {
cin >> N >> K;
K++;
rep(i, N) cin >> B[i+1];
rep(i, N) B[i+1] += B[i];
rep(i, N+1) rep(j, K+1) pre[i][j] = -1;
if (N <= 300) {
rep(i, N+1) rep(j, K+1) dp[i][j] = INF, pre[i][j] = -1;
dp[0][0] = 0;
for (int x=1; x<=N; x++) {
rep(k, K) {
rep(y, x) {
if (dp[y][k] == INF) continue;
long long v = 1LL*B[x]*B[x] + (dp[y][k] + 1LL*B[y]*B[y] - 2LL*B[x]*B[y]);
if (dp[x][k+1] > v) {
dp[x][k+1] = v;
pre[x][k+1] = y;
}
}
}
}
long long m = (1LL*B[N]*B[N]-dp[N][K])/2LL;
cout << m << "\n";
int p = pre[N][K], k = K-1;
vector<int> seq;
while (k > 0) {
seq.pb(p);
p = pre[p][k];
k--;
}
reverse(all(seq));
for (int x : seq) cout << x << " "; cout << "\n";
return 0;
}
ConvexHullTrick cht;
cht.add(0, 0, 0);
long long dp = 0;
rep(k, K) {
ConvexHullTrick ncht;
for (int x=1; x<=N; x++) {
P p = cht.f(-2LL*B[x]);
dp = 1LL*B[x]*B[x] + p._2;
pre[x][k+1] = min((int)p._1, x-1);
//pre[x][k+1] = min(index(B, B+N+1, p._1+1)-1, x-1);
ncht.add(B[x], dp + 1LL*B[x]*B[x], x);
}
cht.ps.clear();
cht.ps.shrink_to_fit();
swap(cht, ncht);
}
long long m = (1LL*B[N]*B[N]-dp)/2LL;
cout << m << "\n";
int p = pre[N][K], k = K-1;
//cout<<"p="<<p<<"\n";
vector<int> seq;
while (k > 0) {
seq.pb(p);
p = pre[p][k];
k--;
}
reverse(all(seq));
for (int x : seq) cout << x << " "; cout << "\n";
return 0;
}
