#include <iostream>
#include <vector>
#include <deque>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const int MAXK = 205;
ll prefix[MAXN];
ll dp[2][MAXN];
int parent[MAXK][MAXN];
struct Line {
ll m, c;
int id;
ll eval(ll x) { return m * x + c; }
};
// Kiểm tra đường thẳng l2 có trở nên vô dụng giữa l1 và l3 không
bool is_bad(Line l1, Line l2, Line l3) {
// Giao điểm (l1, l2) >= Giao điểm (l2, l3)
return (double)(l2.c - l1.c) * (l2.m - l3.m) >= (double)(l3.c - l2.c) * (l1.m - l2.m);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
ll a;
cin >> a;
prefix[i] = prefix[i - 1] + a;
}
int cur = 1, prev = 0;
for (int i = 1; i <= k; i++) {
deque<Line> dq;
// Đường thẳng khởi tạo từ trạng thái trước đó
// Với i=1, dp[prev][0] = 0, prefix[0] = 0
dq.push_back({prefix[i - 1], dp[prev][i - 1] - prefix[i - 1] * prefix[i - 1], i - 1});
for (int j = i; j <= n; j++) {
// Tìm đường thẳng tối ưu nhất cho x = prefix[j]
while (dq.size() >= 2 && dq[0].eval(prefix[j]) <= dq[1].eval(prefix[j])) {
dq.pop_front();
}
dp[cur][j] = dq[0].eval(prefix[j]);
parent[i][j] = dq[0].id;
// Thêm đường thẳng mới vào tập ứng cử viên cho bước sau
Line newLine = {prefix[j], dp[prev][j] - prefix[j] * prefix[j], j};
while (dq.size() >= 2 && is_bad(dq[dq.size() - 2], dq.back(), newLine)) {
dq.pop_back();
}
dq.push_back(newLine);
}
swap(cur, prev);
}
// Xuất kết quả
cout << dp[prev][n] << "\n";
// Truy vết
int curr_n = n;
for (int i = k; i >= 1; i--) {
curr_n = parent[i][curr_n];
cout << curr_n << (i == 1 ? "" : " ");
}
cout << endl;
return 0;
}
