在只因王国内，每个只因都佩戴着一串有N颗只因蛋的只因环。每个只因蛋都有一个头标记和一个尾标记，并且对于相邻的两颗只因蛋，前一颗只因蛋的尾标记必定等于后一颗只因蛋的头标记。只因可以通过吸盘将两颗只因蛋靠近爆炸成一颗新的只因蛋，同时释放出可被吸盘吸收的能量。如果一颗只因蛋的头标记为m，尾标记为r，后一颗只因蛋的头标记为r，尾标记为n，则靠近后爆炸释放出m×r×n单位的能量，形成的只因蛋头标记为m，尾标记为n。
现在需要设计一种最优的靠近顺序，使得一串只因环靠近后只剩下一颗只因蛋释放出的总能量最大。
第一行一个正整数n
第二行 n个不超过1000的正整数，第i个数为第i颗只因蛋的头标记，当i≠n时第 i 颗只因蛋的尾标记等于第 i+1 颗只因蛋的头标记，当i=n时第i颗只因蛋的尾标记等于第1颗只因蛋的头标记。
至于只因蛋的顺序，你可以这样确定：将只因环放在桌面上，随机指定一颗只因蛋为第一颗只因蛋，按顺时针确定其它只因蛋的顺序。
输出只有一行，一个不超过2.1×10^9的正整数，表示最优靠近顺序下所释放的最大能量值。
输入
4 2 3 5 10
输出
710
对于100%的数据，4≤n≤100。
对于样例：4颗只因蛋的头标记和尾标记依次为(2,3) (3,5) (5,10) (10,2)，可以按照如下的靠近顺序：先靠近下标为3和下标为0的只因蛋，爆炸释放10*2*3的能量，得到(3,5) (5,10) (10,3)，再靠近下标为2和下标为0的只因蛋，爆炸释放10*3*5的能量，得到(5,10) (10,5)，最后靠近下标为1和下标为0的只因蛋，爆炸释放10*5*10的能量，总释放能量为710
