#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int getChar();
inline int readChar();
inline void readString(char* out);
template <class T = int>
inline T readInt();
template <class T>
inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeString(const char* s);
constexpr int kInBufSize = 1 << 18;
constexpr int kOutBufSize = 1 << 8;
int opt[201][100001];
ll p[100001];
ll dp[2][100001];
int dq[100001];
int s, e, t;
void prt(int i, int j){
if(i-1)prt(i-1, opt[i][j]);
writeInt(opt[i][j], ' ');
}
int main(){
int n = readInt(), k = readInt();
for(int i = 1; i <= n; i++){
p[i] = p[i-1] + readInt();
}
for(int i = 1; i <= k; i++, t = !t){
s = e = 0;
for(int j = i; j <= n; j++){
while(s < e && p[j]*p[dq[s]]+dp[t][dq[s]]-p[dq[s]]*p[dq[s]] <= p[j]*p[dq[s+1]]+dp[t][dq[s+1]]-p[dq[s+1]]*p[dq[s+1]])s++;
dp[!t][j] = 1LL * p[j] * p[dq[s]] + dp[t][dq[s]] - 1LL * p[dq[s]] * p[dq[s]];
opt[i][j] = dq[s];
while(s < e && (p[j]-p[dq[e-1]]) * (dp[t][dq[e]]-dp[!t][j]+(p[j]-p[dq[e]])*p[dq[e]]) <= (p[j]-p[dq[e]]) * (dp[t][dq[e-1]]-dp[!t][j]+(p[j]-p[dq[e-1]])*p[dq[e-1]]))e--;
dq[++e] = j;
}
}
writeInt(dp[t][n], '\n');
prt(k, n);
}
/* FastIO */
// https://github.com/justiceHui/AlgorithmImplement/blob/master/misc/FastInput.cpp
inline int getChar() {
static char buf[kInBufSize];
static int len = 0, pos = 0;
if (pos == len) pos = 0, len = fread(buf, 1, kInBufSize, stdin);
if (pos == len) return -1;
return buf[pos++];
}
inline int readChar() {
int c = getChar();
while (c <= 32) c = getChar();
return c;
}
inline void readString(char* out) {
int c = getChar();
while (c <= 32) c = getChar();
do {
*(out++) = c;
c = getChar();
} while (c > 32);
*out = 0;
}
template <class T>
inline T readInt() {
int s = 1, c = readChar();
T x = 0;
if (c == '-') s = -1, c = getChar();
while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
return s == 1 ? x : -x;
}
static int write_pos = 0;
static char write_buf[kOutBufSize];
inline void writeChar(int x) {
if (write_pos == kOutBufSize)
fwrite(write_buf, 1, kOutBufSize, stdout), write_pos = 0;
write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt(T x, char end) {
if (x < 0) writeChar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n) s[n++] = '0' + x % 10, x /= 10;
while (n--) writeChar(s[n]);
if (end) writeChar(end);
}
inline void writeString(const char* s) {
while (*s) writeChar(*s++);
}
struct Flusher {
~Flusher() {
if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}
} flusher;
