#include <iostream>
#include <vector>
#include <deque>
using namespace std;
//int dp[n+1][k+1]; // maximum score obtainable from 1..i by making j cuts.
//if(j+1 > i) dp[i][j] = irrelevant
//dp[i][j] = max(x = 1..i-1, dp[x][j-1] + (a[i] - a[x])*a[x])
//dp[i][j] = max(x = 1..i-1, dp[x][j-1] + a[i]*a[x] - a[x]*a[x])
// = a[x]*a[i] + dp2[x] - a[x]^2
int main()
{
long long n, k;
cin >> n >> k;
long long a[n+1];
a[0] = 0;
for(long long i = 1; i <= n; i++)
{
cin >> a[i];
a[i] += a[i-1];
}
//dp
vector<long long> dp2(n+1), dp(n+1);
for(int i = 0; i <= n; i++) dp2[i] = 0; //0 cuts;
deque<long long> A, B, I; // a*x + b
int prev[n+1][k+1];
for(int cuts = 1; cuts <= k; cuts++)
{
A.clear();
B.clear();
I.clear();
I.push_back(1);
A.push_back(a[1]);
B.push_back(dp2[1] - a[1]*a[1]);
for(int i = 2; i <= n; i++)
{
while(A.size() >= 2 && A[0]*a[i] + B[0] < A[1]*a[i] + B[1])
{
I.pop_front();
A.pop_front();
B.pop_front();
}
dp[i] = A[0]*a[i] + B[0];
prev[i][cuts] = I[0];
// cout << prev[i][cuts] << ' ';
// cout << i << " -> " << A[0] << ' ' << B[0] << '\n';
A.push_back(a[i]);
B.push_back(dp2[i] - a[i]*a[i]);
I.push_back(i);
}
// cout << '\n';
swap(dp, dp2);
// for(int i = 1; i <= n; i++) cout << dp2[i] << ' ';
// cout << '\n';
}
cout << dp2[n] << '\n';
int curr = n;
for(int i = k; i >= 1; i--)
{
curr = prev[curr][i];
cout << curr << ' ';
}
cout << '\n';
}
