#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
int n, k;
ll a[maxn];
namespace sub1234{
ll dp[maxn][203];
void trace(int i, int ik) {
if (ik == 1) return;
for (int j = i - 1; j > 0; --j)
if (dp[i][ik] == dp[j][ik - 1] + (a[i] - a[j]) * a[j]) {
trace(j, ik - 1);
cout << j << ' ';
break;
}
}
void run() {
for (int i = 1; i <= n; ++i)
for (int ik = 2; ik <= k + 1 && ik <= i; ++ik)
for (int j = 1; j < i; ++j)
dp[i][ik] = max(dp[i][ik], dp[j][ik - 1] + (a[i] - a[j]) * a[j]);
cout << dp[n][k + 1] << '\n';
trace(n, k + 1);
}
}
namespace sub56{
void xuli(int& i, int& j, int& k) {
int l = j + 1, r = k - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (a[k] - a[mid] >= a[mid - 1] - a[i])
l = mid;
else
r = mid - 1;
}
j = l;
}
void run() {
vector < int > id(k + 1);
for (int i = 0; i <= k; ++i)
id[i] = i;
id.push_back(n);
while (1) {
bool flag = 1;
for (int i = 0; i < k; ++i)
if (id[i + 2] - id[i + 1] > 1) {
ll A = a[id[i + 1]] - a[id[i]], B = a[id[i + 2]] - a[id[i + 1] + 1];
if (B <= A) continue;
flag = 0;
xuli(id[i], id[i + 1], id[i + 2]);
break;
}
if (flag) break;
}
ll ans = 0;
for (int i = 2; i <= k + 1; ++i)
ans += (a[id[i]] - a[id[i - 1]]) * a[id[i - 1]];
cout << ans << '\n';
for (int i = 1; i <= k; ++i)
cout << id[i] << ' ';
}
}
int main(){
#define TASK "ABC"
// freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
ios_base::sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
a[i] += a[i - 1];
//sub56::run(); return 0;
if (n <= 1000)
sub1234::run();
else
sub56::run();
return 0;
}
