题目描述

给定一个具有$\red{N（N<50）}$个顶点（从$\red{1}$到$\red{N}$编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成$\red{N-2}$个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？

输入格式

第一行 顶点数$\red{N}$，第二行 $\red{N}$个顶点（从$\red{1}$到$\red{N}$)的权值

输出格式

最小的和的值，各三角形组成的方式

样例

输入样例

5
277 69 82 26 19

输出样例

511157
The formation of 3 triangle:
1 5 2,2 5 3,3 5 4