/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )
/▄/ /█/ /◐/ /▐/ /▌/ /▀/ /░/ / / choose your own style!
***IT'S OUR LONG WAY TO THE OIILLLL***
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀ ░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀ ░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#include <bits/stdc++.h>
using namespace std ;
#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
namespace fastio {template <class T> ostream &operator<<(ostream &os, const vector<T> &container) {for (auto &u : container)os << u << " ";return os;} template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) {return os << p.first << " " << p.second;}template <class T> ostream &operator<<(ostream &os, set<T> const& con) { for (auto &u : con) os << u << " ";return os;} void pr() {} template <typename T, typename... args> void pr(T x, args... tail) {cout << x << " ";pr(tail...);}} using namespace fastio;
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
mt19937_64 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N = 2e5 + 3;
const int M = 1e9 + 7;
struct CHT{
deque < pair < ll , ll > > q;
int del = 0;
ll div(ll a, ll b){
// b2 - b1, k1 - k2
return a / b - ((a ^ b) && (a % b));
}
void add(ll k, ll b){
pii z = make_pair(k, b);
while(q.size() > 1){
pii y = q.back();
pii x = q[q.size() - 2];
if (y.fi == z.fi){
if (y.se >= z.se) return;
q.pop_back();
continue;
}
if (div(z.se - y.se, y.fi - z.fi) <= div(y.se - x.se, x.fi - y.fi)) q.pop_back();
else break;
}
q.pb(z);
}
pair < ll , int > get(ll X){
while(q.size() > 1){
pii x = q[0];
pii y = q[1];
if (x.F * X + x.S <= y.F * X + y.S) q.pop_front(); else break;
++del;
}
return make_pair(q[0].F * X + q[0].S, del);
}
};
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef Estb_probitie
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
ll a[n], pref[n];
for (int i = 0; i < n; ++i){
cin >> a[i];
pref[i] = a[i];
if (i) pref[i] += pref[i - 1];
}
ll dp[n][k + 1] = {};
int Pr[n][k + 1];
CHT all[k + 2];
for (int i = 0; i + 1 < n; ++i)
all[1].add(pref[i], - pref[i] * pref[i]);
for (int K = 1; K <= k; ++K){
all[K + 1].add(pref[0], 0 - a[0] * a[0]);
for (int i = 1; i < n; ++i){
auto func = all[K].get(pref[i]);
dp[i][K] = func.F;
Pr[i][K] = func.S;
if (i + 1 < n)
all[K + 1].add(pref[i], dp[i][K] - pref[i] * pref[i]);
// cout<<dp[i][K]<<" "<<i<<endl;
}
}
int v = n - 1;
cout << dp[v][k]<<endl;
for (int i = k; i > 0; --i){
v = Pr[v][i];
cout << v + 1 << " ";
}
}
