#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG_INF = (ll)-9e18;
const ll INF = (ll)9e18;
const int MAXK = 205;
const int MAXN = 100000;
int n, k;
ll a[MAXN + 5];
ll pre[MAXN + 5];
int trace_pos[MAXN + 5][MAXK]; // trace_pos[i][c] = best t for dp[i][c]
ll dp[MAXN + 5][MAXK]; // dp[i][c] = min sumsq for prefix i into c parts
struct line {
long long a, b;
mutable long double p;
int id;
bool operator < (const line& other) const {
if (other.a == (long long)1e18 && other.b == (long long)1e18)
return p < other.p;
return a < other.a || (a == other.a && b < other.b);
}
};
struct LINE_CONTAINER {
multiset<line> ms;
inline bool del(multiset<line>::iterator x, multiset<line>::iterator y){
if (y == ms.end()){
x->p = 1e18;
return false;
}
if (x->a == y->a){
x->p = (x->b >= y->b) ? 1e18 : -1e18;
} else {
x->p = (long double)(y->b - x->b) / (long double)(x->a - y->a);
}
return x->p >= y->p;
}
inline void update(long long a, long long b, int i){
auto x = ms.insert({a, b, 0.0L, i});
auto y = next(x);
while (del(x, y)) y = ms.erase(y);
if (x != ms.begin()){
y = prev(x);
if (del(y, x)) ms.erase(x);
} else y = x;
while (y != ms.begin()){
x = prev(y);
if (del(x, y)){
del(x, ms.erase(y));
y = x;
} else break;
}
}
inline pair<long long,int> get(long long x){
auto it = ms.lower_bound({(long long)1e18, (long long)1e18, (long double)x, 0});
if (it == ms.end()) return {NEG_INF, 0};
return { it->a * x + it->b, it->id };
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
if (!(cin >> n >> k)) return 0;
for (int i = 1; i <= n; ++i) { cin >> a[i]; pre[i] = pre[i-1] + a[i]; }
// dp[0][0]=0, rest = INF
for (int i = 0; i <= n; ++i)
for (int c = 0; c <= k+1; ++c) {
dp[i][c] = INF;
trace_pos[i][c] = 0;
}
dp[0][0] = 0;
// c = number of parts (1 .. k+1)
for (int c = 1; c <= k+1; ++c){
LINE_CONTAINER lc;
// We want min_t (dp[t][c-1] + pre[t]^2 - 2*pre[i]*pre[t]).
// To reuse max-CHT, store lines with a' = 2*pre[t], b' = -(dp[t][c-1] + pre[t]^2),
// then max(a'*x + b') = - min(dp[t][c-1] + pre[t]^2 - 2*pre[t]*x).
// So dp[i][c] = pre[i]^2 - max(...) and trace = id of that line.
// Insert line for t=0 first (if valid)
if (dp[0][c-1] < INF/4) lc.update(2LL*pre[0], -(dp[0][c-1] + pre[0]*pre[0]), 0);
for (int i = 1; i <= n; ++i){
auto g = lc.get(pre[i]);
if (g.first != NEG_INF){
ll val = pre[i]*pre[i] - g.first; // dp[i][c]
if (val < dp[i][c]){
dp[i][c] = val;
trace_pos[i][c] = g.second;
}
}
// add line for t = i to be used for later i' > i
if (dp[i][c-1] < INF/4){
ll slope = 2LL * pre[i];
ll intercept = -(dp[i][c-1] + pre[i]*pre[i]);
lc.update(slope, intercept, i);
}
}
}
ll total = pre[n]*pre[n];
ll min_sumsq = dp[n][k+1];
ll best_points = (total - min_sumsq) / 2; // (S^2 - sum sq)/2
cout << best_points << '\n';
// reconstruct cuts: backtrack from (n, k+1)
vector<int> cuts;
int cur = n, c = k+1;
while (c > 0 && cur > 0){
int prev = trace_pos[cur][c];
if (prev == 0) break;
cuts.push_back(prev);
cur = prev;
--c;
}
reverse(cuts.begin(), cuts.end());
// We need exactly k cut positions between 1 and n-1: cuts should contain k positions.
// If cuts contains fewer (some prev were 0), fill none — but normally problem constraints guarantee a solution.
for (size_t i = 0; i < cuts.size() && (int)i < k; ++i){
if (i) cout << ' ';
cout << cuts[i];
}
cout << '\n';
return 0;
}
