题目描述

Serling公司购买长钢条，将其切割成短钢条进行出售。切割工序本身没有成本支出。管理层希望得到最优的切割方法。

现在我们知道Serling公司出售一段长度为i英寸的钢条的价格为pi(i=1,2,3,...,n)，单位为美元。钢条的长度都为整英寸。


给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,3,...,n)，求切割钢条的方案，使得收益q最大化。

输入格式

第一行输入一个n代表长度为n英寸

第二行有N个整数，第i个整数代表长度为i英寸的钢条的价格

输出格式

第一行输出两个整数，代表最大的收益Q和分割后钢条的条数M

第二行从小到大输出M个整数，分别代表分割后每段钢条的长度(若存在相同收益的情况下，输出钢条条数最多的答案）

10
1 5 8 9 10 17 18 20 24 30

30 1
10