Задача №111123. Доставка
Город Прямой Рог, который пока что не находится на территории Российской Федерации, представляет собой одну прямую улицу. В городе работает компания, которая занимается доставкой товаров. Для удобства, адреса доставки представлены в виде чисел, которые задают расстояние от офиса компании. Положительные числа в одну сторону, а отрицательные – в другую. Заказы на доставку выполняются компанией последовательно, в том порядке, в котором они были заданы. В компании работает два курьера. В начале рабочего дня заказы распределяются между ними, и каждый отправляется по своему маршруту. Компании необходимо так спланировать распределение заказов, чтобы суммарное расстояние, которое будет пройдено курьерами на момент выполнения последнего заказа, была минимальным. Напишите программу, которая по расстояниям адресатов от офиса компании находит наименьшее суммарное расстояние, которое пройдут ее работники.
Первая строка входных данных содержит целое число N (1 ≤ N ≤ 100 000) — количество заказов. Далее следует N строк, каждая из которых содержит одно целое число — расстояние от офиса до адресата. Если расстояние положительное — то адресат находится в одной части города относительно офиса компании, а если отрицательное, то в другой. Расстояния по модулю не превышают 108.
Единственная строка должна содержать одно целое число — минимально возможное суммарное расстояние, которое пройдут оба работника компании.
5
1
-1
2
-2
3
5