Wookje Is a Devoted Son!!

Time limit2sMemory limit512 MB

Summary

Given edge costs of a cycle of n villages, find the minimum total cost for three travelers starting at one village to collectively visit every village.

Level: Medium4 of 10
Topics: Greedy, Implementation, Array, Brute force
Solved: No attempts yet

Problem

To mark the occasion of bombing the KOI, Wookje went on a trip to Codegate Island with his parents. Codegate Island has many tourist spots, such as Junoh Village, famous for its squid (not Junoh Lim the grumpy hacker), Jaehoon Village, famous for its rice, and Youngjoong Village. Wookje wants to take his parents around Codegate Island.

The villages of Codegate Island lie in a circle along the coast. To go from any village A to any village B, you travel around the island along the coast, taking either the road to the left or the road to the right. There is no road other than this circular one around the island.

You are given the travel cost between each pair of neighboring villages. Tell Wookje the minimum travel cost he needs to prepare so that he and his parents can visit every village on the island.

Input

The first line contains the number of villages $n$ . ( $1 \le n \le 50{,}000$ )

The second line contains $n$ travel costs $v_i$ . $v_i$ is the travel cost between village $i$ and village $i+1$ , and the $n$ -th value $v_n$ is the travel cost between village $n$ and village $1$ . ( $1 \le v_i \le 1{,}000$ )

Output

Print the minimum travel cost needed to visit every village.

Examples2

Example 1
Input
```
5
1 6 5 2 4
```
Expected output
```
12
```
Example 2
Input
```
4
100 100 100 101
```
Expected output
```
300
```