#include<bits/stdc++.h>
using namespace std;
#define int long long
void File() {
#define file "test"
freopen(file".in", "r", stdin);
freopen(file".out", "w", stdout);
}
int arr[100001];
int pf[100001];
int n;
int DP[100001][201];
int trace[100001][201];
int gs(int l, int r)
{
if (l > r) return 0;
return pf[r] - pf[l - 1];
}
int cost(int l, int r, int k)
{
return DP[l][k - 1] + gs(l + 1, r) * gs(r + 1, n);
}
void divide(int l, int r, int gL, int gR, int k)
{
if (l > r) return;
int mid = (l + r) / 2;
int bestPos = gL;
for (int i = gL; i <= min(mid, gR); i++)
{
if (cost(i, mid, k) > cost(bestPos, mid, k)) bestPos = i;
}
DP[mid][k] = cost(bestPos, mid, k);
trace[mid][k] = bestPos;
divide(l, mid - 1, gL, bestPos, k);
divide(mid + 1, r, bestPos, gR, k);
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//File();
int k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
pf[i] = pf[i - 1] + arr[i];
}
for (int i = 1; i <= n; i++) DP[i][1] = gs(1, i) * gs(i + 1, n);
for (int i = 2; i <= k; i++) divide(1, n, 1, n, i);
int ans = -1e18;
int bestPos = n;
int temp = k;
vector <int> res;
for (int i = 1; i <= n; i++)
{
if (DP[i][k] > ans)
{
ans = DP[i][k];
bestPos = i;
}
}
res.push_back(bestPos);
while (trace[bestPos][temp] != 0)
{
bestPos = trace[bestPos][temp];
temp--;
res.push_back(bestPos);
}
cout << ans << endl;
for (int x : res) cout << x << " ";
return 0;
}
/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⢿⣿⣿⠿⠛⠿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠉⠄⣀⡤⢤⣤⣈⠁⣠⡔⠶⣾⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡿⠛⠋⠁⠄⠄⠄⣼⣿⠁⡀⢹⣿⣷⢹⡇⠄⠎⣿⣿⣿
⣿⣿⣿⠿⠛⠉⠁⠄⠄⠄⠄⠄⠄⠄⠹⣇⣀⣡⣾⣿⡿⠉⠛⠒⠒⠋⠉⢸
⡿⠋⠁⠄⠄⢀⣤⣤⡀⠄⠄⠄⠄⠄⠄⠈⠙⠛⠛⠉⠄⠄⠄⠄⠄⠄⠄⠈
⠄⠄⠄⠄⠄⢹⣧⡈⠿⣷⣄⣀⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣠⢄⣾
⠄⠄⠄⠄⠄⠈⠻⢿⣶⣌⣙⡛⠛⠿⠶⠶⠶⠶⠶⠖⣒⣒⣚⣋⡩⢱⣾⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠈⠉⠛⠛⠛⠻⠿⠿⠟⠛⠛⠛⠉⢉⣥⣶⣾⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠒⠶⣿⣿⣿⣿⣿⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿
⣿⡿⠛⠛⠛⢻⣿⠿⠛⠛⠛⢿⣿⣿⡿⠛⠛⠛⢻⡟⠛⣿⡿⠛⣻⣿⣿⣿
⡟⠄⣼⣿⣿⣿⡇⠄⣾⣿⣧⠄⢻⡏⠄⣼⣿⣿⣿⡇⠄⡟⢀⣴⣿⣿⣿⣿
⡇⠄⣿⣿⣿⣿⡄⠄⣿⣿⣿⠄⢸⡇⠄⣿⣿⣿⣿⡇⠄⣀⠈⢻⣿⣿⣿⣿
⣿⣄⠈⠙⠛⢻⣧⡄⠙⠛⠉⣠⣿⣷⣄⠈⠙⠛⢹⡇⠄⣿⣧⠄⠻⣿⣿⣿
___ ___ _________ ________ ___ ___ ________ ________ ________ ________ ________ ________ ________
|\ \|\ \|\___ ___\ |\ __ \|\ \|\ \|\ __ \|\ ___ \|\ ____\ |\ __ \|\ ____\|\ __ \|\ __ \
\ \ \\\ \|___ \ \_| \ \ \|\ \ \ \\\ \ \ \|\ \ \ \\ \ \ \ \___| \ \ \|\ \ \ \___|\ \ \|\ /\ \ \|\ \
\ \ __ \ \ \ \ \ \ ____\ \ __ \ \ \\\ \ \ \\ \ \ \ \ ___ \ \ \\\ \ \ \ \ \ __ \ \ \\\ \
\ \ \ \ \ \ \ \ \ \ \___|\ \ \ \ \ \ \\\ \ \ \\ \ \ \ \|\ \ \ \ \\\ \ \ \____\ \ \|\ \ \ \\\ \
\ \__\ \__\ \ \__\ \ \__\ \ \__\ \__\ \_______\ \__\\ \__\ \_______\ \ \_______\ \_______\ \_______\ \_______\
\|__|\|__| \|__| \|__| \|__|\|__|\|_______|\|__| \|__|\|_______| \|_______|\|_______|\|_______|\|_______|
*/
