【问题描述】
在你的帮助下，G调整好了石块和荷叶的位置。D和Z踩着石块过了池塘，却发现G不见了。
原来G被大Boss捉走了。
大Boss有一种很厉害的武器，叫做能量球，它是由许多能量珠合成的。大Boss的能量球刚好用完了，他捉来了G，让G为他制作能量球。
能量球的制作方式如下：
现在有一串能量珠，每次合并两个相邻的能量珠，得到的新能量珠的能量为两个能量珠能量之和。而最终得到的大能量球的能量为每次得到的新能量珠的能量总和。
G知道，大Boss制作能量球是为了对付D和Z，所以她会尽量使得她制作的能量球能量值尽量小。
【输入格式】
共2行。
第1行一个整数n（1≤n≤200），表示共n个能量珠。
第2行n个整数，表示一串能量珠，其中第1颗和最后一颗能量珠是相连接的。
【输出格式】
一个整数，表示最小能量值。
【样例输入】
4
4 5 9 4
【样例输出】
43
在你的帮助下，G调整好了石块和荷叶的位置。D和Z踩着石块过了池塘，却发现G不见了。
原来G被大Boss捉走了。
大Boss有一种很厉害的武器，叫做能量球，它是由许多能量珠合成的。大Boss的能量球刚好用完了，他捉来了G，让G为他制作能量球。
能量球的制作方式如下：
现在有一串能量珠，每次合并两个相邻的能量珠，得到的新能量珠的能量为两个能量珠能量之和。而最终得到的大能量球的能量为每次得到的新能量珠的能量总和。
G知道，大Boss制作能量球是为了对付D和Z，所以她会尽量使得她制作的能量球能量值尽量小。
【输入格式】
共2行。
第1行一个整数n（1≤n≤200），表示共n个能量珠。
第2行n个整数，表示一串能量珠，其中第1颗和最后一颗能量珠是相连接的。
【输出格式】
一个整数，表示最小能量值。
【样例输入】
4
4 5 9 4
【样例输出】
43
