//https://www.instagram.com/_modwwe/
//#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
void phongbeo();
const ll inf=1e9;
const int mod2=1e9+7;
const int mod1=998244353;
struct icd
{
long double a;
int b;
};
struct ib
{
ll a;
ll b;
};
struct ic
{
int a,b,c;
};
struct id
{
int a,b,c,d;
};
struct ie
{
int a,b,c,d,e;
};
ll n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
int i,s10,s12;
int kk;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
// fin(task),fou(task);
#endif
NHP
/// cin>>s1;
// modwwe
phongbeo();
}
int dp[201][100001];
int a[100001];
ib ss;
ib c[201][100001];
void calc(int x,int l,int r,int l2,int r2)
{
if(l>r) return;
int mid=l+r>>1;
int pos=-1;
int res=-inf;
for(int i=l2;i<=min(r2,mid-1);i++)
{
if(dp[x-1][i]+(a[mid]-a[i])*(a[n]-a[mid])>res)
{
res=dp[x-1][i]+(a[mid]-a[i])*(a[n]-a[mid]);;
pos=i;
c[x][mid]={x-1,i};
}
}
if(res>s8)
s8=res,ss={x,mid};
dp[x][mid]=res;
calc(x,l,mid-1,l2,pos);
calc(x,mid+1,r,pos,r2);
}
vector<int> v;
void phongbeo()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i],a[i]+=a[i-1];
for(int i=1;i<=m;i++)
{
calc(i,1,n,1,n);
}
cout<<s8,down
while(ss.a!=0)
{ v.pb(ss.b);
ss=c[ss.a][ss.b];
assert(ss.a>=0);
}
reverse(v.begin(),v.end());
for(auto x:v)
cout<<x<<" ";
}
