#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;
using ld = long double;
#define N 200002
#define ALL(x) x.begin(), x.end()
int n, k, a[N];
ll p[N];
int bt[202][N];
/*
* dp[j][i] = 0..i with j-th split happening at between a[i] and a[i+1]
*
* dp[j][i] = max(dp[j-1][k] + (p[i] - p[k]) * (p[n] - p[i]))
* = p[i]p[n] - p[i]p[i] + max(p[i]p[k] + dp[j-1][k] - p[k]p[n])
**/
struct line
{
ll m, c; int id;
ll operator[](ll x) { return m*x+c; }
ll intersectx(const line &l) {
if (l.m == m)
{
if (c > l.c) return -1e18;
return 1e18;
}
return (c-l.c)/(l.m-m);
}
};
struct ConvexHullTrick : deque<line>
{
void add(line l)
{
while (size() > 1 && back().intersectx((*this)[size()-2]) > back().intersectx(l)) pop_back();
push_back(l);
}
line query(ll x)
{
while (size() > 1 && front().intersectx((*this)[1]) <= x) pop_front();
return front();
}
} cht[2];
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i], p[i] = p[i-1] + a[i];
ll dp;
cht[0].add(line{0, 0, -1});
for (int j = 1; j <= k + 1; ++j)
{
cht[j&1].clear();
for (int i = 1; i <= n; ++i)
{
line lne = cht[!(j&1)].query(p[i]);
dp = p[i]*p[n] - p[i]*p[i] + lne[p[i]];
bt[j][i] = lne.id;
cht[j&1].add(line{p[i], dp - p[i]*p[n], i});
}
}
deque<int> path;
for (int c = bt[k+1][n], j = k; c != -1;)
path.push_front(c), c = bt[j--][c];
cout << dp << '\n';
for (auto x : path) cout << x << ' ';
return 0;
}
