Description

在世界遥远的地方，有一片香蕉林。许多可爱的猴子住在那里。一天，香蕉森林之王SDH决定举办一场盛大的聚会来庆祝疯狂香蕉节。但是小猴子们彼此不认识，所以作为国王，SDH必须做点什么。

现在有$n$只猴子围成一圈坐着，每只猴子都有一个交朋友的时间。而且，每只猴子都有两个邻居。SDH想要将他们相互介绍，规则是:

1.每次，他只能介绍一只猴子和这只猴子的邻居。

2.如果他引入了A和B，那么每只A已经知道的猴子也会知道B已经知道的猴子，引入的总时间是A和B已经知道的所有猴子交朋友时间的总和;

3.每只小猴子都认识自己;

为了尽快开始聚会和吃香蕉，SDH想知道他需要介绍的最小时间。

Input Format

第一行是$n$($1≤n≤1000$)，这是猴子的数量。

下一行包含$n$个正整数(小于1000)，表示交友时间(按顺序，第一个和最后一个是邻居)。

Output Format

输出一个数表示SDH介绍的最小时间。

8 
5 2 4 7 6 1 3 9

105