\begin{problem}{Завоеватель}{conquest.in}{conquest.out}{2 секунды}{256 мегабайт}

%Автор задачи: Павел Кротков
%Автор условия: Анна Малова
                
\setlength{\epigraphwidth}{.7\textwidth}
\epigraph{
И я видел, что Агнец снял первую из семи печатей, и я услышал одно из четырёх животных, говорящее как бы громовым голосом: иди и смотри.\\Я взглянул, и вот, 
конь белый, и на нем всадник, имеющий лук, и дан был ему венец;\\
и вышел он как победоносный, и чтобы победить.}{Откровение Иоанна Богослова}

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

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

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

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

\Examples
\begin{example}%
\exmp{
6
3 4 3 2 1 5
}{
12
}%
\end{example}

\Note
Решения, работающие в случаях, в которых $n$ не превышает $100$, будут оцениваться в $60$ баллов.

\end{problem}
