#1885. 分蛋糕

分蛋糕

题目描述

经过漫长的等待,小云雀杯终于要开始了。参赛的同学们收到礼品之后热情高涨,都拿出了十二分的精神去面对比赛。当大家读完第一题时,就产生了浓厚的兴趣。

题目是这样的:有一个n\red{n}边形的蛋糕,依次按顺时针的方向对各个顶点进行标号(1\red{1,}2\red{2,}…,n\red{n)},现在要将蛋糕切成n2\red{n-2}份(每切一次都必须从顶点开始到另一个顶点结束)。i\red{i}代表第i\red{i}份蛋糕,ai\red{a_i}代表第i\red{i}份蛋糕的顶点乘积。怎样切蛋糕,才能使i=1n2ai\red{\sum\limits_{i=1}^{n-2}{a_i}}值最小呢?

输入格式

共一行,输入数字n(n<=500)\red{n(n<=500)}

输出格式

共一行,输出乘积和的最小值。

样例

输入样例1

3

输出样例1

6

输入样例2

4

输出样例2

18

提示

对于数据2\red{2},小Z进行 1×2×3+1×3×4\red{1\times2\times3 + 1\times3\times4 }切割的

20%\red{20\%}的数据 n<=10\red{n<=10}

40%\red{40\%}的数据 n<=100\red{n<=100}

60%\red{60\%}的数据 n<=300\red{n<=300}

80%\red{80\%}的数据 n<=400\red{n<=400}

100%\red{100\%}的数据 n<=500\red{n<=500}