#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 int N = (int) 1e5;
const int MAXK = (int) 200;
int a[N + 2];
int n , k;
namespace subtask1{
bool check(){
return n <= 1000;
}
const int maxn = (int) 1e3;
int trace[maxn + 2][MAXK + 2] = {};
LL dp[maxn + 2][MAXK + 2];
LL pre[maxn + 2] = {};
void main_code(){
for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
memset(dp,-0x3f,sizeof dp);
dp[0][0] = 0;
++k;
for(int i = 1; i <= n; ++i) {
for(int used = 1; used <= k; ++used){
for(int t = 0; t < i; ++t) {
if (maximize(dp[i][used] , dp[t][used - 1] + (pre[n] - pre[i]) * (pre[i] - pre[t]))){
trace[i][used] = t;
}
}
}
}
cout << dp[n][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 << ' ';
}
}
namespace subtask2{
bool check(){
return n <= N;
}
LL dp[N + 2][MAXK + 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) {};
};
struct Hull{
Line x;
long double intersec;
};
long double get_intersec(Line x , Line y){
return (long double)(y.b - x.b) / (long double)(x.a - y.a);
}
LL F(Line a , LL x){
return a.a * x + a.b;
}
class Convex_Hull{
public:
vector<Hull>line;
void insert_line(Line x){
int sz = sz(line) ;
while (sz >= 2 && line[sz - 1].intersec >= get_intersec(x , line[sz - 2].x)) {
line.pop_back();
--sz;
}
if (line.empty()) line.push_back({x , LLONG_MIN});
else {
line.push_back({x , get_intersec(line[sz - 1].x , 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 = 0 , high = sz(line) - 1 , p = 0;
while (low <= high){
int mid = (low + high) / 2;
if (line[mid].intersec <= val){
p = mid;
low = mid + 1;
}
else high = mid - 1;
}
return {F(line[p].x , val) , line[p].x.id};
}
};
Convex_Hull cover[MAXK + 2];
void main_code(){
for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
memset(dp , -0x3f , sizeof dp);
cover[0].add_line(0 , 0 , 0);
++k;
for(int i = 1; i <= n; ++i){
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[i][used] = kq.first - pre[i] * pre[i] + pre[n] * pre[i];
trace[i][used] = kq.second;
cover[used].add_line(pre[i] , dp[i][used] - pre[n] * pre[i] , i);
}
}
cout << dp[n][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 (subtask1::check()) return subtask1::main_code() , 0;
// if (subtask2::check()) return subtask2::main_code() , 0;
return 0;
}
