#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, k, a[maxn + 1], pre[maxn + 1], trace[maxn + 1][201];
long long dp[maxn + 1][201], bestPos = 0;;
struct line {
long long a, b;
mutable long double p;
int id;
bool operator<(const line& other) const { return a < other.a; }
bool operator<(long double x) const { return p < x; } // for heterogeneous lookup
};
struct LINE_CONTAINER {
multiset<line, less<>> ms;
static constexpr long double INF = 1e30L;
inline bool isect(multiset<line, less<>>::iterator x, multiset<line, less<>>::iterator y){
if (y == ms.end()){
x->p = INF;
return false;
}
if (x->a == y->a){
x->p = (x->b >= y->b) ? INF : -INF;
}
else x->p = (long double)(y->b - x->b) / (long double)(x->a - y->a);
return x->p >= y->p;
}
inline void update(long long a, long long b, int i){
auto x = ms.insert({a, b, 0.0L, i});
auto y = next(x);
while(isect(x, y)) y = ms.erase(y);
if (x != ms.begin()){
y = prev(x);
if (isect(y, x)) { ms.erase(x); return; }
} else y = x;
while(y != ms.begin()){
x = prev(y);
if (isect(x, y)){
isect(x, ms.erase(y));
y = x;
}
else break;
}
}
inline pair<long long, int> get(long long X){
if (ms.empty()) return {LLONG_MIN/4, 0};
auto it = ms.lower_bound((long double)X); // uses operator<(long double)
if (it == ms.end()) --it;
return { it->a * X + it->b, it->id };
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i){
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
vector<LINE_CONTAINER> lc(k);
lc[0].update(0, 0, 0);
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= k; ++j) {
dp[i][j] = -1e18;
trace[i][j] = 0;
}
dp[0][0] = 0;
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= min(i, k); ++j){
pair<long long, int> g = lc[j - 1].get(pre[n] - pre[i]);
dp[i][j] = g.first + pre[i] * (pre[n] - pre[i]);
if (j < k && dp[i][j] > -1e18) lc[j].update(-(long long)pre[i], dp[i][j], i);
if (j == k && i < n && dp[i][k] > dp[bestPos][k]) bestPos = i;
trace[i][j] = g.second;
}
}
cout << dp[bestPos][k] << '\n';
int curPos = bestPos;
int curK = k;
vector<int> cuts;
while (curPos != 0 && curK > 0) {
cuts.push_back(curPos);
int prev = trace[curPos][curK];
curPos = prev;
--curK;
}
reverse(cuts.begin(), cuts.end());
for (int x : cuts) cout << x << ' ';
return 0;
}
