#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i , a , b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1) << (x))
#define BIT(mask , x) (((mask)>>(x))&(1))
#define sz(x) (int)(x).size()
template<class T1 , class T2>
bool maximize(T1 &a , T2 b){
if (a < b) return a = b , true; else return false;
}
template<class T1 , class T2>
bool minimize(T1 &a , T2 b){
if (a > b) return a = b , true; else return false;
}
template<class T>
void compress(vector<T>&data){
sort(data.begin() ,data.end());
data.resize(unique(data.begin() , data.end()) - data.begin());
}
template<class T1 , class T2>
T2 Find(const vector<T1>&data , T2 y){
return upper_bound(data.begin() , data.end() , y) - data.begin();
}
const LL inf = (LL) 1e18;
const int N = (int) 1e5;
const int MAXK = (int) 200;
int a[N + 2];
int n , k;
namespace subtask2{
bool check(){
return n <= N;
}
LL dp[N + 2] = {} , g[N + 2] = {};
int trace[N + 2][MAXK + 2];
LL pre[N + 2] = {};
struct Line{
LL a , b ;
int id;
Line() {};
Line(LL a , LL b , int id) : a(a) , b(b) , id(id) {};
};
class Convex_Hull{
public:
vector<Line>line;
int p = 1;
bool compare1(Line a , Line b , Line c){
LL t1 = (b.b - a.b) , t2 = (c.b - a.b);
LL x1 = (a.a - b.a) , x2 = (a.a - c.a);
return t1 * x2 >= t2 * x1;
}
bool compare2(Line a , Line b , LL t){
LL t1 = (b.b - a.b) , t2 = (a.a - b.a);
return t1 >= t * t2;
}
LL F(Line a , LL x){
return a.a * x + a.b;
}
void insert_line(Line x){
int sz = sz(line) ;
while (sz >= 2 && compare1(line[sz - 2] , line[sz - 1] , x)) {
line.pop_back();
--sz;
}
line.push_back(x);
return;
}
void add_line(LL a , LL b , int id){
insert_line(Line(a , b , id));
return;
}
pair<LL,int> Find(LL val){
int low = 1 , high = sz(line) - 1 , p = 0;
while (low <= high){
int mid = (low + high) / 2;
if (compare2(line[mid - 1] , line[mid] , val)){
p = mid;
low = mid + 1;
}
else high = mid - 1;
}
return {F(line[p] , val) , line[p].id};
}
};
void solve(int idx){
for(int i = 0; i <= n; ++i) dp[i] = LLONG_MIN;
Convex_Hull cover;
for(int i = 0; i <= n; ++i){
if (sz(cover.line)){
pair<LL,int> kq = cover.Find(pre[i]);
dp[i] = kq.first - pre[i] * pre[i] + pre[n] * pre[i];;
trace[i][idx] = kq.second;
}
if (g[i] >= 0) cover.add_line(pre[i] , g[i] - pre[n] * pre[i] , i);
}
for(int i = 0; i <= n; ++i) g[i] = dp[i];
}
void main_code(){
for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
int old_n = n;
++k;
int turn = 0;
g[0] = 0;
for(int i = 1; i <= k; ++i) solve(i);
cout << g[n] << '\n';
vector<int>border;
while (n){
border.push_back(n);
n = trace[n][k] ;
--k;
}
reverse(border.begin() , border.end());
border.pop_back();
LL ans = 0;
for(int i = 0; i < border.size(); ++i){
if (i == 0) ans = pre[border[i]] * (pre[old_n] - pre[border[i]]);
else ans = ans + (pre[border[i]] - pre[border[i - 1]]) * (pre[old_n] - pre[border[i]]);
}
assert(ans == g[old_n]);
for(auto& x : border) cout << x << ' ';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0) ;
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
cin >> n >> k;
for(int i = 1; i <= n; ++i) cin >> a[i];
if (subtask2::check()) return subtask2::main_code() , 0;
return 0;
}
