#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define endl '\n';
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define py cout << "YES" << endl;
#define pn cout << "NO" << endl;
#define pb push_back
#define int long long
typedef long double lld;
#define double lld
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 1e18;
const ll mod = 1e9+7;
const int N = 2e5;
vector<int>primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
void judge(){
srand(time(NULL));
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
freopen("Error.txt", "w", stderr);
#define debug(x...) cerr << #x <<" = "; _print(x); cerr << endl;
#else
#define debug(x...)
#endif
}
void usaco(string s) {
freopen((s + ".in").c_str(),"r",stdin);
freopen((s + ".out").c_str(),"w",stdout);
}
struct IOPre
{
static constexpr int TEN = 10, SZ = TEN * TEN * TEN * TEN;
std::array<char, 4 * SZ> num;
constexpr IOPre() : num{}
{
for (int i = 0; i < SZ; i++)
{
int n = i;
for (int j = 3; j >= 0; j--)
{
num[i * 4 + j] = static_cast<char>(n % TEN + '0');
n /= TEN;
}
}
}
};
struct IO
{
#if !HAVE_DECL_FREAD_UNLOCKED
#define fread_unlocked fread
#endif
#if !HAVE_DECL_FWRITE_UNLOCKED
#define fwrite_unlocked fwrite
#endif
static constexpr int SZ = 1 << 17, LEN = 32, TEN = 10, HUNDRED = TEN * TEN,
THOUSAND = HUNDRED * TEN, TENTHOUSAND = THOUSAND * TEN,
MAGIC_MULTIPLY = 205, MAGIC_SHIFT = 11, MASK = 15,
TWELVE = 12, SIXTEEN = 16;
static constexpr IOPre io_pre = {};
std::array<char, SZ> input_buffer, output_buffer;
int input_ptr_left, input_ptr_right, output_ptr_right;
IO()
: input_buffer{},
output_buffer{},
input_ptr_left{},
input_ptr_right{},
output_ptr_right{} {}
IO(const IO &) = delete;
IO(IO &&) = delete;
IO &operator=(const IO &) = delete;
IO &operator=(IO &&) = delete;
~IO() { flush(); }
template <class T>
struct is_char
{
static constexpr bool value = std::is_same_v<T, char>;
};
template <class T>
struct is_bool
{
static constexpr bool value = std::is_same_v<T, bool>;
};
template <class T>
struct is_string
{
static constexpr bool value =
std::is_same_v<T, std::string> || std::is_same_v<T, const char *> ||
std::is_same_v<T, char *> || std::is_same_v<std::decay_t<T>, char *>;
};
template <class T, class D = void>
struct is_custom
{
static constexpr bool value = false;
};
template <class T>
struct is_custom<T, std::void_t<typename T::internal_value_type>>
{
static constexpr bool value = true;
};
template <class T>
struct is_default
{
static constexpr bool value = is_char<T>::value || is_bool<T>::value ||
is_string<T>::value ||
std::is_integral_v<T>;
};
template <class T, class D = void>
struct is_iterable
{
static constexpr bool value = false;
};
template <class T>
struct is_iterable<
T, typename std::void_t<decltype(std::begin(std::declval<T>()))>>
{
static constexpr bool value = true;
};
template <class T, class D = void, class E = void>
struct is_applyable
{
static constexpr bool value = false;
};
template <class T>
struct is_applyable<T, std::void_t<typename std::tuple_size<T>::type>,
std::void_t<decltype(std::get<0>(std::declval<T>()))>>
{
static constexpr bool value = true;
};
template <class T>
static constexpr bool needs_newline = (is_iterable<T>::value ||
is_applyable<T>::value) &&
(!is_default<T>::value);
template <typename T, typename U>
struct any_needs_newline
{
static constexpr bool value = false;
};
template <typename T>
struct any_needs_newline<T, std::index_sequence<>>
{
static constexpr bool value = false;
};
template <typename T, std::size_t I, std::size_t... Is>
struct any_needs_newline<T, std::index_sequence<I, Is...>>
{
static constexpr bool value =
needs_newline<decltype(std::get<I>(std::declval<T>()))> ||
any_needs_newline<T, std::index_sequence<Is...>>::value;
};
inline void load()
{
memmove(std::begin(input_buffer),
std::begin(input_buffer) + input_ptr_left,
input_ptr_right - input_ptr_left);
input_ptr_right =
input_ptr_right - input_ptr_left +
static_cast<int>(fread_unlocked(
std::begin(input_buffer) + input_ptr_right - input_ptr_left, 1,
SZ - input_ptr_right + input_ptr_left, stdin));
input_ptr_left = 0;
}
inline void read_char(char &c)
{
if (input_ptr_left + LEN > input_ptr_right)
load();
c = input_buffer[input_ptr_left++];
}
inline void read_string(std::string &x)
{
char c;
while (read_char(c), c < '!')
continue;
x = c;
while (read_char(c), c >= '!')
x += c;
}
inline void read_string(char *a)
{
char c;
while (read_char(c), c < '!')
continue;
*(a++) = c;
while (read_char(c), c >= '!')
*(a++) = c;
}
template <class T>
inline std::enable_if_t<std::is_integral_v<T>, void> read_int(T &x)
{
if (input_ptr_left + LEN > input_ptr_right)
load();
char c = 0;
do
c = input_buffer[input_ptr_left++];
while (c < '-');
[[maybe_unused]] bool minus = false;
if constexpr (std::is_signed<T>::value == true)
if (c == '-')
minus = true, c = input_buffer[input_ptr_left++];
x = 0;
while (c >= '0')
x = x * TEN + (c & MASK), c = input_buffer[input_ptr_left++];
if constexpr (std::is_signed<T>::value == true)
if (minus)
x = -x;
}
inline void skip_space()
{
if (input_ptr_left + LEN > input_ptr_right)
load();
while (input_buffer[input_ptr_left] <= ' ')
input_ptr_left++;
}
inline void flush()
{
fwrite_unlocked(std::begin(output_buffer), 1, output_ptr_right, stdout);
output_ptr_right = 0;
}
inline void write_char(char c)
{
if (output_ptr_right > SZ - LEN)
flush();
output_buffer[output_ptr_right++] = c;
}
inline void write_bool(bool b)
{
if (output_ptr_right > SZ - LEN)
flush();
output_buffer[output_ptr_right++] = b ? '1' : '0';
}
inline void write_string(const std::string &s)
{
for (auto x : s)
write_char(x);
}
inline void write_string(const char *s)
{
while (*s)
write_char(*s++);
}
inline void write_string(char *s)
{
while (*s)
write_char(*s++);
}
template <typename T>
inline std::enable_if_t<std::is_integral_v<T>, void> write_int(T x)
{
if (output_ptr_right > SZ - LEN)
flush();
if (!x)
{
output_buffer[output_ptr_right++] = '0';
return;
}
if constexpr (std::is_signed<T>::value == true)
if (x < 0)
output_buffer[output_ptr_right++] = '-', x = -x;
int i = TWELVE;
std::array<char, SIXTEEN> buf{};
while (x >= TENTHOUSAND)
{
memcpy(std::begin(buf) + i,
std::begin(io_pre.num) + (x % TENTHOUSAND) * 4, 4);
x /= TENTHOUSAND;
i -= 4;
}
if (x < HUNDRED)
{
if (x < TEN)
{
output_buffer[output_ptr_right++] = static_cast<char>('0' + x);
}
else
{
std::uint32_t q =
(static_cast<std::uint32_t>(x) * MAGIC_MULTIPLY) >>
MAGIC_SHIFT;
std::uint32_t r = static_cast<std::uint32_t>(x) - q * TEN;
output_buffer[output_ptr_right] = static_cast<char>('0' + q);
output_buffer[output_ptr_right + 1] =
static_cast<char>('0' + r);
output_ptr_right += 2;
}
}
else
{
if (x < THOUSAND)
{
memcpy(std::begin(output_buffer) + output_ptr_right,
std::begin(io_pre.num) + (x << 2) + 1, 3),
output_ptr_right += 3;
}
else
{
memcpy(std::begin(output_buffer) + output_ptr_right,
std::begin(io_pre.num) + (x << 2), 4),
output_ptr_right += 4;
}
}
memcpy(std::begin(output_buffer) + output_ptr_right,
std::begin(buf) + i + 4, TWELVE - i);
output_ptr_right += TWELVE - i;
}
template <typename T_>
IO &operator<<(T_ &&x)
{
using T = typename std::remove_cv<
typename std::remove_reference<T_>::type>::type;
static_assert(is_custom<T>::value or is_default<T>::value or
is_iterable<T>::value or is_applyable<T>::value);
if constexpr (is_custom<T>::value)
{
write_int(x.get());
}
else if constexpr (is_default<T>::value)
{
if constexpr (is_bool<T>::value)
{
write_bool(x);
}
else if constexpr (is_string<T>::value)
{
write_string(x);
}
else if constexpr (is_char<T>::value)
{
write_char(x);
}
else if constexpr (std::is_integral_v<T>)
{
write_int(x);
}
}
else if constexpr (is_iterable<T>::value)
{
// strings are immune
using E = decltype(*std::begin(x));
constexpr char sep = needs_newline<E> ? '\n' : ' ';
int i = 0;
for (const auto &y : x)
{
if (i++)
write_char(sep);
operator<<(y);
}
}
else if constexpr (is_applyable<T>::value)
{
// strings are immune
constexpr char sep =
(any_needs_newline<
T, std::make_index_sequence<std::tuple_size_v<T>>>::value)
? '\n'
: ' ';
int i = 0;
std::apply(
[this, &sep, &i](auto const &...y)
{
(((i++ ? write_char(sep) : void()), this->operator<<(y)),
...);
},
x);
}
return *this;
}
template <typename T>
IO &operator>>(T &x)
{
static_assert(is_custom<T>::value or is_default<T>::value or
is_iterable<T>::value or is_applyable<T>::value);
static_assert(!is_bool<T>::value);
if constexpr (is_custom<T>::value)
{
typename T::internal_value_type y;
read_int(y);
x = y;
}
else if constexpr (is_default<T>::value)
{
if constexpr (is_string<T>::value)
{
read_string(x);
}
else if constexpr (is_char<T>::value)
{
read_char(x);
}
else if constexpr (std::is_integral_v<T>)
{
read_int(x);
}
}
else if constexpr (is_iterable<T>::value)
{
for (auto &y : x)
operator>>(y);
}
else if constexpr (is_applyable<T>::value)
{
std::apply([this](auto &...y)
{ ((this->operator>>(y)), ...); }, x);
}
return *this;
}
IO *tie(std::nullptr_t) { return this; }
void sync_with_stdio(bool) {}
};
IO io;
#define cin io
#define cout io
struct line {
mutable int m, c, p;
int pos;
bool operator<(const line& l) const { return m < l.m; }
bool operator<(int x) const { return p < x; }
};
// Returns max for a convex hull
struct LineContainer : multiset<line, less<>> {
// (for doubles, use inf = 1/.0, ceil(a,b) = a/b)
int div(int a, int b) { // floored division
return a / b - ((a ^ b) < 0 && a % b);
}
bool isect(iterator x, iterator y) {
if (y == end()){
x -> p = inf;
return false;
}
if (x->m==y->m){
x->p = -1*inf;
if (x->c > y->c) {
x->p = inf;
}
}
else{
x->p = div(y->c - x->c, x->m - y->m);
}
return x->p >= y->p;
}
void add(int m, int c, int idx) {
auto it = insert({m, c, 0, idx}) , next = it++, prev = next;
while (isect(next, it)){
it = erase(it);
}
if (prev != begin() && isect(--prev, next)){
isect(prev, next = erase(next));
}
while ((next = prev) != begin() && (--prev)->p >= next->p){
isect(prev, erase(next));
}
}
pair<int,int> query(int x) {
auto l = *lower_bound(x);
return {l.m * x + l.c,l.pos};
}
};
signed main(){
fastio; //judge();
int n,k; cin >> n >> k;
k++;
vector<int>a(n);
for(auto &x : a) cin >> x;
int sum = accumulate(a.begin(),a.end(),0);
vector<int>dp1(n);
vector<vector<int>>pos(n,vector<int>(k+1,-1));
vector<int>pref(n);
int curr = 0;
for(int i = 0;i<n;i++){
curr += a[i];
dp1[i] = curr*curr;
pos[i][1] = 0;
pref[i] = curr;
}
vector<int>dp2(n);
for(int kx = 2;kx<=k;kx++){
LineContainer cht;
for(int i = kx-2;i<=kx-2;i++){
cht.add(2*pref[i],-1*(pref[i]*pref[i] + dp1[i]),i);
}
for(int i = kx-1;i<n;i++){
curr = a[i];
pair<int,int>tmp = cht.query(pref[i]);
dp2[i] = pref[i]*pref[i] - 1*tmp.first;
pos[i][kx] = tmp.second;
cht.add(2 * pref[i], -1 * (pref[i] * pref[i] + dp1[i]), i);
}
dp1 = dp2;
}
cout << (sum*sum - dp1[n-1])/2 << endl;
int num = n-1;
vector<int>ordering;
for(int i = k;i>=2;i--){
ordering.pb(pos[num][i]+1);
num = pos[num][i];
}
reverse(ordering.begin(),ordering.end());
for(auto x : ordering)
cout << x << ' ';
}
