题目描述
经过漫长的等待,小云雀杯终于要开始了。参赛的同学们收到礼品之后热情高涨,都拿出了十二分的精神去面对比赛。当大家读完第一题时,就产生了浓厚的兴趣。
题目是这样的:有一个n边形的蛋糕,依次按顺时针的方向对各个顶点进行标号(1,2,…,n),现在要将蛋糕切成n−2份(每切一次都必须从顶点开始到另一个顶点结束)。i代表第i份蛋糕,ai代表第i份蛋糕的顶点乘积。怎样切蛋糕,才能使i=1∑n−2ai值最小呢?
输入格式
共一行,输入数字n(n<=500)。
输出格式
共一行,输出乘积和的最小值。
样例
输入样例1
3
输出样例1
6
输入样例2
4
输出样例2
18
提示
对于数据2,小Z
进行 1×2×3+1×3×4切割的
20%的数据 n<=10
40%的数据 n<=100
60%的数据 n<=300
80%的数据 n<=400
100%的数据 n<=500