29354번 - Завоеватель 다국어

문제

И я видел, что Агнец снял первую из семи печатей, и я услышал одно из четырёх животных, говорящее как бы громовым голосом: иди и смотри.

Я взглянул, и вот, конь белый, и на нем всадник, имеющий лук, и дан был ему венец;

и вышел он как победоносный, и чтобы победить.

Откровение Иоанна Богослова

Первый всадник Апокалипсиса Завоеватель пришел на Землю. Увидели это жители одного города и решили предупредить свою столицу, дабы ее жители успели покаяться. С этой целью жителями города в столицу был отправлен гонец на лошади.

Дорога между этим городом и столицей представляет собой прямую, на которой, включая этот город и столицу, расположены $n$ городов, причем расстояние между любыми соседними городами на этой прямой одинаково. В каждом из $n - 2$ городов, мимо которых гонцу необходимо проехать, он может сменить лошадь в конюшне. Хозяин каждой конюшни знает, сколько минут требуется лошади в этой конюшне на дорогу между двумя соседними городами. За какое минимальное время гонец сможет добраться до столицы ($n$-го города на этой прямой)?

입력

В первой строке входного файла содержится одно целое число $n$ (1ドル \le n \le 100{,円}000$) --- количество городов. В следующей строке содержатся $n$ натуральных чисел $t_i$ (1ドル \le t_i \le 10^6$) --- количество минут, необходимое лошади из конюшни в $i$-ом городе на преодоление расстояния между двумя городами. Заметим, что первое число означает скорость лошади, которая была у гонца при выезде из первого города, а последнее --- скорость лошади в конюшне столицы.

출력

В выходной файл выведите одно число --- количество минут, за которое гонец доедет до столицы.

제한

힌트