3022 - 猴子派对

森林之王决定举办一个盛大的派对来庆祝香蕉节，但是小猴子们都不认识对方。有 n 只猴子坐在一个圈里，每只猴子都有交朋友的时间，并且每只猴子都有两个邻居。介绍它们的规则是：

1、森林之王每次都可以介绍一只猴子和该猴子的一个邻居；
2、若森林之王介绍A和B，则A已经认识的每只猴子都将认识B已经认识的每只猴子，介绍的总时间是A和B已经认识的所有猴子交友时间的总和；
3、每只猴子都认识自己。

为了尽快开始聚会和吃香蕉，想知道森林之王需要介绍的最短时间。

输入包含几个测试用例。
每个测试用例的第 1 行都是 n（1≤n≤300），表示猴子的数量。下一行包含 n 个正整数（小于300），表示交朋友的时间（第1个和最后1个是邻居）。

对每个测试用例，都单行输出需要介绍的最短时间。