在火星上,每位火星人都佩戴着一串能量项链,项链由 颗能量珠首尾相连构成(形成一个环)。第 颗珠子拥有 头标记 ; 尾标记 (下标对 取模,令 )。 当相邻两颗珠子 满足 时,可通过聚合操作将二者合成为一颗新珠子,并释放能量 . 新珠子的头标记为 ,尾标记为 。 火星人可以按任意顺序不断聚合相邻珠子,直至项链上只剩下一颗珠子。不同的聚合顺序会导致总能量不同。请设计一种聚合顺序,使释放的总能量最大。
输入描述:
第一行输入一个整数 ——珠子数量。第二行输入 个正整数 ——珠子的头标记。输入保证对所有 都满足 等于第 颗珠子的尾标记,而第 颗珠子的尾标记等于 。


输出描述:
输出一个整数 ——在最优聚合方案下释放的最大能量。
示例1

输入

4
2  3  5  10

输出

710

说明

\hspace{15pt}一种最优聚合顺序如下(用 \oplus 表示聚合):
\hspace{23pt}\bullet\, B_4\oplus B_1 释放能量 10\times2\times3=60
\hspace{23pt}\bullet\, (B_4\oplus B_1)\oplus B_2 释放能量 10\times3\times5=150
\hspace{23pt}\bullet\, ((B_4\oplus B_1)\oplus B_2)\oplus B_3 释放能量 10\times5\times10=500
\hspace{15pt}总能量 60+150+500=710,可证明这是最大值。
加载中...