//https://dmoj.ca/problem/apio14p2
// ~~ icebear love attttt ~~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class T>
bool minimize(T &a, const T &b) {
if (a > b) return a = b, true;
return false;
}
template<class T>
bool maximize(T &a, const T &b) {
if (a < b) return a = b, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebearat"
const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 1e5 + 5;
int n, k, a[N], trace[N][205];
ll dp_before[N], dp_cur[N], pref[N];
class ConvexHullTrick {
private:
struct Line {
long long a, b;
int id;
Line (long long _a = 0, long long _b = 0, int _id = 0):
a(_a), b(_b), id(_id) {}
long long eval(long long x) {
return a * x + b;
}
};
deque<Line> hull;
bool bad(Line l1, Line l2, Line l3) {
// assert(l1.a != l2.a);
// assert(l1.a != l3.a);
/**
if intersect of (l1, l3) < intersect of (l1, l2) then we dont need to use l2
because f_i(x) will better with l1 or l3
*/
return (l3.b - l1.b) * (l1.a - l2.a) <= (l1.a - l3.a) * (l2.b - l1.b);
}
void eraseLine(long long x) {
while(hull.size() >= 2 && hull[0].eval(x) <= hull[1].eval(x)) hull.pop_front();
}
public:
void reset() { hull.clear(); }
void addLine(long long a, long long b, int id) {
Line l = Line(a, b, id);
while(hull.size() >= 2 && bad(hull[hull.size() - 2], hull.back(), l))
hull.pop_back();
hull.push_back(l);
}
pair<long long, int> query(long long x) {
/**
find max f_i(x)
*/
assert(hull.size());
eraseLine(x);
return make_pair(hull[0].eval(x), hull[0].id);
}
} CHT;
void init(void) {
cin >> n >> k;
FOR(i, 1, n) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
}
void process(void) {
memset(dp_before, -0x3f, sizeof dp_before);
const ll NEG_INF = dp_before[0];
dp_before[0] = 0;
k++;
FOR(j, 1, k) {
memset(dp_cur, -0x3f, sizeof dp_cur);
CHT.reset();
FOR(i, j, n) {
if (dp_before[i - 1] != NEG_INF)
CHT.addLine(pref[i - 1], dp_before[i - 1] - pref[i - 1] * pref[n], i - 1);
auto cht = CHT.query(pref[i]);
if (maximize(dp_cur[i], cht.first + pref[i] * (pref[n] - pref[i])))
trace[i][j] = cht.second;
}
FOR(i, 0, n) dp_before[i] = dp_cur[i];
}
cout << dp_cur[n] << endl;
while(n && k > 1) {
cout << (n = trace[n][k--]) << ' ';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int tc = 1;
// cin >> tc;
while(tc--) {
init();
process();
}
return 0;
}
