#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N_ = 100500;
const int K_ = 205;
int N, K; ll S[N_];
ll table[2][N_];
int rev[K_][N_];
ll sq(ll a) { return a * a; }
deque<int> deq;
int main() {
scanf("%d%d", &N, &K); ++K;
for (int i = 1; i <= N; i++) {
int x; scanf("%d", &x);
S[i] = S[i - 1] + x;
}
// min sum {s^2}
for (int i = 1; i <= N; i++) table[1][i] = sq(S[i]);
for (int k = 2; k <= K; k++) {
ll *cur = table[k & 1];
ll *prv = table[~k & 1];
for (int i = 1; i <= N; i++) cur[i] = prv[i];
deq.clear();
cur[k] = prv[k - 1] + sq(S[k] - S[k - 1]);
rev[k][k] = k - 1;
deq.push_back(k - 1);
if(S[k] != S[k-1]) deq.push_back(k);
for (int i = k + 1; i <= N; i++) {
// get best
{
while (deq.size() > 1) {
int a = deq[0], b = deq[1];
lf ix = (lf)(prv[b] - prv[a] + sq(S[b]) - sq(S[a])) / (2 * S[b] - 2 * S[a]);
if (S[i] <= ix) break;
deq.pop_front();
}
}
// update
{
int j = deq.front();
cur[i] = (prv[j] + sq(S[j])) - 2 * S[j] * S[i] + sq(S[i]);
rev[k][i] = j;
}
// insert line
{
while (deq.size() > 1) {
int t = *deq.rbegin();
if (S[t] == S[i]) break;
int l = *++deq.rbegin();
lf i1 = (lf)(prv[l] - prv[t] + sq(S[l]) - sq(S[t])) / (2 * S[l] - 2 * S[t]);
lf i2 = (lf)(prv[i] - prv[t] + sq(S[i]) - sq(S[t])) / (2 * S[i] - 2 * S[t]);
if (i1 > i2) deq.pop_back();
else {
deq.push_back(i);
break;
}
}
}
}
}
/*for (int k = 2; k <= K; k++) {
for (int i = k; i <= N; i++) {
// naive
printf("tb[%d,%d] = %lld -> ", k,i,table[k][i]);
table[k][i] = table[k - 1][i];
for (int j = k - 1; j < i; j++) {
ll cur = (table[k - 1][j] + sq(S[j])) - 2 * S[j] * S[i] + sq(S[i]);
// ----------------constant -----기울기 ---x좌표 --------상관X
table[k][i] = min(table[k][i], cur);
}
printf("%lld\n", table[k][i]);
}
}*/
printf("%lld\n", (sq(S[N]) - table[K & 1][N]) / 2);
vector<int> rec;
for (int i = K, j = N; i > 0;) {
if(i < K) rec.push_back(j);
j = rev[i--][j];
}
reverse(rec.begin(), rec.end());
for (int x : rec) printf("%d ", x);
return 0;
}
