욱제는 효도쟁이야!!

욱제는 KOI를 망친 기념으로 부모님과 함께 코드게이트 섬으로 여행을 떠났다. 코드게이트 섬에는 오징어로 유명한 준오마을(심술쟁이 해커 임준오 아님), 밥으로 유명한 재훈마을, 영중마을 등 관광지가 많다. 욱제는 부모님을 모시고 코드게이트 섬을 관광하려고 한다.

코드게이트 섬의 마을은 해안가를 따라 원형으로 놓여 있다. 어떤 마을 A에서 다른 마을 B로 가려면 왼쪽이나 오른쪽 도로를 타고 해안가를 따라 섬을 돌아야 한다. 섬을 도는 이 원형 도로 말고 다른 길은 없다.

이웃한 두 마을 사이의 이동비용이 주어진다. 욱제가 부모님을 모시고 섬의 모든 마을을 관광할 때, 준비해야 하는 최소 이동비용을 구하자.

첫째 줄에 마을의 수 $n$이 주어진다. ($1 \le n \le 50{,}000$)

둘째 줄에 이동비용 $v_i$가 $n$개 주어진다. $v_i$는 $i$번째 마을과 $i+1$번째 마을 사이의 이동비용이고, $n$번째 값 $v_n$은 $n$번째 마을과 $1$번째 마을 사이의 이동비용이다. ($1 \le v_i \le 1{,}000$)

모든 마을을 관광하는 데 필요한 최소 이동비용을 출력한다.