29552번 - Доставка 다국어

Серёжа --- обычный мальчик. Его родители работают курьерами в фирме <<Koni Express>>. Фирма занимается доставкой наборов из кубиков по всем городам страны Лайнландии. В стране находятся $N + 1$ городов, выстроенных на одной прямой. Соседние города соединены между собой дорогами. На каждой дороге стоит дом, в котором живет хозяин дома. Хозяева обычно собирают плату за проезд по дороге, на которой стоит их дом, однако некоторые пропускают курьеров бесплатно, а некоторые даже согласны платить путешественникам за то, что они проехали по их дороге и пожелали удачи хозяину (в этом случае сумма платы просто отрицательна).

Изначально каждый хозяин дома хочет приобрести один набор из кубиков. Родители Сережи находятся в разных концах страны. Папа перед первым домом, а мама за последним. За одну поездку каждый из них может довезти только один набор, причем будет невежливо ехать с набором дальше, чем до первого дома с еще необслуженным покупателем. За проезд только до своего дома и назад, хозяева денег не берут, но и не дают.

Сережа --- сообразительный мальчик. Его родители решили обратиться к нему за помощью. Ему была поставлена задача --- посчитать, в какую минимальную сумму обойдется им доставка наборов во все дома. И он попросил Вас помочь ему.

В первой строке входного файла содержится одно целое число $N$ ($1 \le N \le 10^6$).

Во второй строке содержатся $N$ целых чисел $a_i$ ($|a_i| \le 10^4$) --- сумма, взимаемая хозяином дома с номером $i$.

Выведите единственное число --- минимальное количество рублей, которые родители Сережи потратят на доставку, или же отрицательное значение, если они еще и заработают.

В первом примере папе выгодно доставить в первый и второй дома, а маме в третий и четвертый. Тогда в сумме они платят по одному разу хозяевам первого и четвертого дома, в сумме --- $2$.

Во втором примере папа доставляет в первый, второй и третий дома, а мама только в четвертый. Тогда только папа платит два раза хозяину первого и один раз хозяину второго дома, в сумме --- $3$.