#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define int long long
#define ld long double
#define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e18 + 9;
const int MAX = 4000 + 5, LOGMAX = 20, B = 441, MOD = 998244353;
struct line{
int k, b;
int f(int x){
return x * k + b;
}
ld inter(line a){
return (ld)(a.b - b) / (ld)(k - a.k);
}
};
void solve(){
int n, k; cin >> n >> k;
k++;
int arr[n + 1];
int pre[n + 1];
pre[0] = 0;
for(int i = 1; i <= n; i++){
cin >> arr[i];
pre[i] = pre[i - 1] + arr[i];
}
vector<int> dp(n + 1, -oo);
dp[0] = 0;
//dp[i] = (dp[j] - pre[j] * pre[j]) + pre[i] * pre[j];
vector<signed> par[k + 1];
for(int j = 1; j <= k; j++){
vector<int> ndp(n + 1, -oo);
par[j].resize(n + 1, 0);
deque<line> dq;
deque<int> id;
dq.push_back({pre[j - 1], (dp[j - 1] - pre[j - 1] * pre[j - 1])});
id.push_back(j - 1);
for(int i = j; i <= n; i++){
while(dq.size() >= 2 && dq[0].f(pre[i]) < dq[1].f(pre[i])){
dq.pop_front();
id.pop_front();
}
ndp[i] = dq[0].f(pre[i]);
par[j][i] = id[0];
if(dp[i] < 0) continue;
line a = {pre[i], dp[i] - pre[i] * pre[i]};
while(dq.size() >= 2 && a.k != dq.back().k && a.inter(dq[dq.size()-2]) <= dq.back().inter(dq[dq.size()-2])){
dq.pop_back();
id.pop_back();
}
while(dq.size() && a.k == dq.back().k && a.b >= dq.back().b){
dq.pop_back();
id.pop_back();
}
if(!dq.size() || dq.back().k != a.k){
dq.push_back(a);
id.push_back(i);
}
}
swap(ndp, dp);
}
cout << dp[n] << '\n';
vector<int> v;
int i = n;
while(k){
if(i != n) v.push_back(i);
i = par[k][i];
k--;
}
reverse(all(v));
if(!v.size()) v.push_back(1);
for(int a : v) cout << a << ' ';
cout << '\n';
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
}
