#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 100002
#define ALL(x) x.begin(), x.end()
int n, k, a[N];
ll p[N], dp[2][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) { return (c-l.c)/(l.m-m); }
};
struct ConvexHullTrick : deque<line>
{
void add(line l)
{
while (size() > 1 &&
((back().m == l.m && l.c >= back().c) ||
(back().intersectx((*this)[size()-2]) >= back().intersectx(l)))) pop_back();
push_back(l);
}
line query(ll x)
{
while (size() > 1 && front()[x] <= (*this)[1][x]) pop_front();
return front();
}
};
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];
ConvexHullTrick cht;
for (int j = 1; j <= k + 1; ++j)
{
cht.add(line{0, 0, -1});
for (int i = 1; i <= n; ++i)
{
line lne = cht.query(p[i]);
dp[j&1][i] = p[i]*p[n] - p[i]*p[i] + lne[p[i]];
bt[j][i] = lne.id;
if (j != 1) cht.add(line{p[i], dp[!(j&1)][i] - p[i]*p[n], i});
}
cht.clear();
}
deque<int> path;
for (int c = bt[k+1][n], j = k; j >= 0 && c != -1;) path.push_front(c), c = bt[j--][c];
cout << dp[(k+1)&1][n] << '\n';
for (auto x : path) cout << x << ' ';
return 0;
}
