#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct line
{
ll a,b,ind;
ll operator()(ll x)
{
return a + b*x;
}
pll operator*(line& other)
{
return {other.a - a,b - other.b};
}
};
deque<line> hull;
ll arr[100001];
ll pref[100001];
void add_line(line l)
{
while(siz(hull) >= 2)
{
line l1 = hull.front();
hull.pop_front();
line l2 = hull.front();
hull.pop_front();
pll com = l1*l2;
pll com2 = l1*l;
if(com.ss < 0)
{
com.ff *= -1;
com.ss *= -1;
}
if(com2.ss < 0)
{
com2.ff *= -1;
com2.ss *= -1;
}
if(com.ff * com2.ss < com2.ff * com.ss && (com2.ss != 0 || l.b < l1.b))
{
hull.push_front(l2);
hull.push_front(l1);
break;
}
else
{
hull.push_front(l2);
}
}
if(siz(hull) == 0)
{
hull.push_front(l);
}
else
{
if(hull.front().b != l.b)
{
hull.push_front(l);
}
else
{
if(hull.front().a < l.a)
{
hull.pop_front();
hull.push_front(l);
}
}
}
if(siz(hull) == 2)
{
line l1 = hull.front();
hull.pop_front();
line l2 = hull.front();
hull.pop_front();
if(l1.b < l2.b) swap(l1,l2);
hull.push_front(l2);
hull.push_front(l1);
}
}
pll get_best(ll x)
{
if(siz(hull) == 0) return {-1e18,-1};
while(siz(hull) >= 2)
{
line fl = hull.back();
hull.pop_back();
line f2 = hull.back();
hull.pop_back();
if(f2(x) >= fl(x))
{
hull.push_back(f2);
}
else
{
hull.push_back(f2);
hull.push_back(fl);
break;
}
}
return {hull.back()(x),hull.back().ind};
}
ll dp[100001];
int best[100001][201];
void PrintHull()
{
vector<line> lines;
while(!hull.empty())
{
line l = hull.back();
hull.pop_back();
lines.pb(l);
}
forall(it,lines) hull.push_front(it);
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
int n,k;
cin >> n >> k;
rep2(i,1,n) cin >> arr[i];
rep2(i,1,n) pref[i] = pref[i-1] + arr[i];
ll sum = 0;
rep2(i,1,n) sum += arr[i];
rep(i,n+1) dp[i] = -1;
dp[0] = 0;
k++;
rep(kk,k)
{
hull = {};
rep(i,n+1)
{
PrintHull();
ll prev_dp = dp[i];
pll b = get_best(pref[i]);
dp[i] = -b.ff + pref[i] * pref[i];
if(b.ff == -1e18) dp[i] = -1;
best[i][kk] = b.ss;
if(prev_dp != -1)
{
add_line({-pref[i]*pref[i]-prev_dp,2*pref[i],i});
}
}
}
cout << (sum*sum - dp[n])/2 << "\n";
vi ans;
int z = k-1;
int cur = n;
rep(i,k-1)
{
ans.pb(best[cur][z]);
cur = best[cur][z];
z--;
}
reverse(all(ans));
forall(it,ans) cout << it << " ";
}
