6. Teleport of elles

Вокруг города эльфов Ривенделла проложена кольцевая дорога – РКАД. Протяжённость её – N эльфийских ярдов. Вдоль дороги стоят эльфоярдовые столбы-порталы: они пронумерованы с 1, за столбом с номером N следует первый, расстояние между столбами, естественно, один эльфийский ярд.

В связи с возросшей активностью орков жители ЗаРКАДья решили перебраться в Ривенделл. Они выходили из дебрей и собирались у магических эльфоярдовых столбов, где и ожидали, когда их телепортируют в город.

Владыка Элронд решил осуществить транспортирвку эльфов так: он выйдет к одному из столбов, прикоснётся к нему – и там окажутся все стоявшие у столбов эльфы. Оттуда их доставка в город будет осуществляться без помощи магии (автобусами). Но вот сбор эльфов к одному столбу потребует существенных затрат магической энергии: затраты на транспортировку одного эльфа в эльфийских Джоулях равняются кратчайшему расстоянию в эльфийских ярдах по РКАД от столба, где эльф, до столба, где Элронд.

Разработайте программу, вычисляющую минимальные энергозатраты Элронда на транспортировку всех эльфов.

Входные данные. В первой строке значение N – количество столбов на РКАД (их не более 50000), далее следуют N строк, в каждой из которых целое неотрицательное число не больше 100 – количество эльфов у очередного столба.