题目描述

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

①森林之王每次都可以介绍一只猴子和该猴子的一个邻居；

②若森林之王介绍$A$和$B$，则$A$已经认识的每只猴子都将认识$B$已经认识的每只猴子，介绍的总时间是$A$和$B$已经认识的所有猴子交友时间的总和；

③每只猴子都认识自己。

为了尽快开始聚会和吃香蕉，需求出森林之王需要介绍的时间。

输入格式

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

输出格式

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

样例

8
5 2 4 7 6 1 3 9

105

来源

HDU3506