#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[2][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;
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 sz = line.size();
while (sz > 1 && compare2(line[sz - 2] , line[sz - 1] , val) == false) line.pop_back() , --sz;
return {F(line[sz - 1] , val) , line[sz - 1].id};
}
};
Convex_Hull cover[MAXK + 2];
void main_code(){
for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
++k;
int turn = 0;
memset(dp[turn] , -0x3f , sizeof dp[turn]);
cover[0].add_line(0 , 0 , 0);
for(int i = 1; i <= n; ++i){
turn = !turn;
memset(dp[turn] , -0x3f , sizeof dp[turn]);
for (int used = k; used >= 1; --used){
if (cover[used - 1].line.size() == 0) continue;
pair<LL,int> kq = cover[used - 1].Find(pre[i]);
dp[turn][used] = kq.first - pre[i] * pre[i] + pre[n] * pre[i];
trace[i][used] = kq.second;
cover[used].add_line(pre[i] , dp[turn][used] - pre[n] * pre[i] , i);
}
}
cout << dp[turn][k] << '\n';
vector<int>border;
while (n){
border.push_back(n);
n = trace[n][k] , --k;
}
reverse(border.begin() , border.end());
border.pop_back();
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;
}
