#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 BIT(mask , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1) << (x))
#define sz(x) (int)(x).size()
#define Time_used cerr << "\n Time lapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
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 T1 , class T2>
T2 Find(const vector<T1>&data , T2 y){
return upper_bound(data.begin() , data.end() , y) - data.begin();
}
template<class T>
void compress(vector<T>&data){
sort(data.begin() , data.end());
data.resize(unique(data.begin() , data.end()) - data.begin());
}
const int N = (int) 1e5;
const LL inf = (LL)4e18;
int a[N + 2];
int n , k;
LL pre[N + 2] = {};
namespace subtask1{
bool check(){
return n <= 200;
}
const int maxn = 200;
int trace[maxn + 2][maxn + 2] = {};
LL dp[maxn + 2][maxn + 2] = {};
void main_code(){
memset(dp , -0x3f , sizeof dp);
dp[0][0] = 0;
++k;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= i; ++j){
for(int turn = 1; turn <= k; ++turn){
LL cc_cost = (pre[i] - pre[j - 1]) * (pre[n] - pre[i]);
if (maximize(dp[i][turn] , dp[j - 1][turn - 1] + cc_cost)) trace[i][turn] = j - 1;
}
}
}
cout << dp[n][k] << '\n';
vector<int> ans;
while(k>0){
ans.push_back(n);
n = trace[n][k]; --k;
}
reverse(ans.begin() , ans.end());
ans.pop_back();
for(auto& x : ans) cout << x << ' '; cout << '\n';
}
}
namespace subtask2{
bool check(){
return true;
}
struct Line{
LL a , b;
int id;
Line(LL a , LL b , int id) : a(a) , b(b) , id(id) {};
};
vector<Line> line;
long double Get_intersec(Line a , Line b){
return (long double)(b.b - a.b) / (a.a - b.a);
}
bool compare_1(Line a , Line b , Line c){
LL x1 = b.a - a.a , x2 = c.a - a.a;
LL y1 = a.b - b.b , y2 = a.b - c.b;
return y1 * x2 > y2 * x1;
}
void insert(Line x){
int n = sz(line);
while (n > 1 && compare_1(line[n - 2] , line[n - 1] , x)){
line.pop_back();
--n;
}
line.push_back(x);
return;
}
bool compare_2(Line a , Line b , LL val){
LL x1 = b.a - a.a , y1 = a.b - b.b;
return y1 <= val * x1;
}
pair<LL,int> F(Line a , LL x){
return {a.a * x + a.b , a.id};
}
int ptr = 0;
pair<LL,int> Find(LL x){
int low = 1 , high = sz(line) - 1 , p = 0;
while (low <= high){
int mid = (low + high) / 2;
if (compare_2(line[mid - 1] , line[mid] , x)){
p = mid;
low = mid + 1;
}
else high = mid - 1;
}
return F(line[p] , x);
}
LL g[N + 2] = {} , dp[N + 2] = {};
const int MAXK = 200;
int trace[N + 2][MAXK+2];
void solve(int turn){
for(int i = 0; i <= n; ++i) dp[i] = -inf;
line.clear();
ptr = 0;
for(int i = 0; i <= n; ++i){
if (sz(line)){
pair<LL,int> kq = Find(pre[i]);
LL cost = kq.first - pre[i] * pre[i] + pre[n] * pre[i];
dp[i] = cost;
trace[i][turn] = kq.second;
}
if (g[i] != -inf) insert(Line(pre[i] , g[i] - pre[n] * pre[i] , i));
}
for(int i = 0; i <= n; ++i) g[i] = dp[i];
return;
}
void main_code(){
++k;
for(int i = 0; i <= n; ++i) g[i] = -inf;
g[0] = 0;
for(int i = 1; i <= k; ++i) {
solve(i);
}
cout << g[n] << '\n';
vector<int> ans;
while(k>0){
ans.push_back(n);
n = trace[n][k]; --k;
}
reverse(ans.begin() , ans.end());
ans.pop_back();
// for(auto& x : ans) cout << x << ' '; cout << '\n';
}
}
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];
for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
// if (subtask1::check()) return subtask1::main_code() , 0;
return subtask2::main_code() , 0;
return 0;
}
