题目描述

HNOI 1997

张琪曼疑惑道:"墨老师。墨家学派的墨家宝库真的藏有对付天顶星人的方法?" 墨老师:"是的,墨家学派的创始人是上古战国时代的墨子,那时墨子就已经对天文学、 几何光学和静力学等进行了深人研究,比如说他认为物体的运动,在时间中表现为先后的差 异,在空间中表现为位置的迁移,离开时空的运动是不存在的。又如对于物体的受力运动， 提出作用力和反作用力,并认为如果没有阻力的话，物体会永远运动下去......"

楚继光惊讶道:"这不是牛顿三定律里的内容吗?他能在上古时代就能想到,好强大。"

墨老师:"虽然作为两大显学之一的墨家学派在后世日渐式微,但墨家精神和墨家传人 一直传承到现在,我们现在要进人的墨家宝库就是其传人秘密建造的工程之一。"

张琪曼:"可是这个宝库打开的条件是:给定一个具有$\red{N(N<50)}$个顶点，从$\red{1}$到$\red{N}$编 号的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成$\red{N-2}$个互不相交的 三角形,使得这些三角形顶点的权的乘积之和最小?这应该怎么计算呢?"

输入格式

第一行为顶点数$\red{N,}$第二行为$\red{N}$个顶点,从$\red{1}$到$\red{N}$的权值。

输出格式

第一行为最小的和的值，

第二行为各三角形组成的方式。各三角形各顶点之间以空格间隔,顶点从小到大排序， 三角形之间从左到右按字典序排序,中间的逗号为半角字符。

样例

输入样例

5
121 122 123 245 231

输出样例

12214884
1 2 3.1 3 5.3 4 5