#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int N = 100003, R = 203;
int dp[R][N]; // store dp[i^1]
struct f{
ll top, bot;
bool operator<=(f b){
return (__int128_t) top*b.bot <= (__int128_t) b.top*bot;
}bool operator<(f b){
return (__int128_t) top*b.bot < (__int128_t) b.top*bot;
}
};
f inter(array<ll,3> a, array<ll,3> b){
f cur = {a[1]-b[1],b[0]-a[0]};
if (cur.bot<0) cur = {-cur.top,-cur.bot};
return cur;
}
int main(){
cin.tie(NULL),cin.sync_with_stdio(false);
int n,k; cin >> n >> k;
vector<ll> a(n);
rep(i,0,n) cin >> a[i];
/*
(ai+1 + ai+2 + ... + aj)^2 = sum a_i^2 + all cross terms
-> we want to minimize cross terms
-> for some position, we have dp[i] + (pref[j] - pref[i])^2
= (dp[i] + pref[i]^2) - 2pref[i]pref[j] + pref[j]^2
pref[j]^2 is constant, and the rest is a linear function
with dequeue in O(k*n) -> elements in linear order
How to retrieve a construction? -> store from in function, only store integers
100000*200*4 bytes ~ 80mb, fits in memory limit
*/
vector<ll> pref(n+1);
rep(i,0,n) pref[i+1] = pref[i] + a[i];
auto get = [&](int l, int r) -> ll {
return pref[r] - pref[l];
};
ll ans;
deque<array<ll,3>> curlines, nxtlines; // ax + b, from
curlines.push_back({0,0,0});
rep(iter,0,k+1){
// -2pref decreases, we want min -> push to end, retrieve from front
swap(nxtlines,curlines);
curlines.clear();
rep(i,0,n){
while(sz(nxtlines)>1 and inter(nxtlines[0],nxtlines[1]) < (f){pref[i+1],1}) nxtlines.pop_front();
ll cur = nxtlines[0][0]*pref[i+1] + nxtlines[0][1] + pref[i+1]*pref[i+1];
if (iter == k and i==n-1) cout << (pref[n]*pref[n] - cur)/2 << '\n';
dp[iter][i+1] = nxtlines[0][2];
array<ll,3> line = {-2*pref[i+1], cur + pref[i+1]*pref[i+1],i+1};
while (sz(curlines)>1 and inter(curlines.back(), line) <= inter(curlines[sz(curlines)-2],curlines.back())) curlines.pop_back();
curlines.push_back(line);
}
}
vi sol;
int at = n;
for(int i = k; i>0; i--){
at = dp[i][at];
sol.push_back(at);
}
reverse(all(sol));
for(auto c : sol) cout << c << ' ';
cout << '\n';
}
