정복자

어린 양이 일곱 인 가운데 첫째 인을 떼는 것을 내가 보았고, 네 생물 가운데 하나가 우레 같은 음성으로 "와서 보라"고 말하는 것을 내가 들었다.

내가 보니 흰 말이 있었고, 그 위에 탄 자는 활을 가졌으며, 그에게 면류관이 주어졌다.

그는 이기는 자로 나아갔고, 또 이기기 위하여 나아갔다.

사도 요한의 계시록

묵시록의 첫 번째 기수인 정복자가 지구에 왔다. 한 도시의 주민들이 이를 보고, 수도의 주민들이 회개할 시간을 갖도록 수도에 알리기로 했다. 이를 위해 이 도시는 말을 탄 전령을 수도로 보냈다.

이 도시와 수도를 잇는 길은 곧은 일직선이다. 이 도시와 수도를 포함해 직선 위에 $n$개의 도시가 놓여 있으며, 인접한 두 도시 사이의 거리는 모두 같다. 전령은 그 사이에 있는 $n - 2$개의 도시를 지나가야 하며, 각 도시의 마구간에서 말을 바꿔 탈 수 있다. 각 마구간의 주인은 자기 마구간의 말이 인접한 두 도시 사이를 가는 데 몇 분이 걸리는지 알고 있다. 전령이 직선 위의 $n$번째 도시인 수도에 도착하기까지 걸리는 최소 시간은 얼마인가?

첫 줄에 도시의 개수 $n$ ($1 \le n \le 100{\,}000$)이 주어진다. 다음 줄에는 자연수 $n$개 $t_i$ ($1 \le t_i \le 10^6$)가 주어진다. $t_i$는 $i$번째 도시 마구간의 말이 인접한 두 도시 사이를 가는 데 걸리는 분이다. 첫 번째 값은 전령이 첫 번째 도시에서 출발할 때 타고 있던 말의 값이고, 마지막 값은 수도 마구간 말의 값이다.

전령이 수도까지 가는 데 걸리는 분을 한 개의 수로 출력한다.