BOI’ 2005 RHODES Island – HELLAS 
3-8 September 2005
Bulgaria
Задача 1: Ветроходна регата

За предстоящата Балканска олимпиада по ветроходство на остров Родос, организационният комитет разработва правила за ветроходна регата от нов тип. Комитетът е поставил известен брой плаващи знаци по права линия на различни разстояния в морето. Всички лодки стартират едновременно от определена точка от тази линия и трябва да посетят всички знаци, разположени по нея. Една лодка приключва участието си след като посети всички знаци. Побеждава онази лодка, която посети всички знаци и натрупа минимална сума от общи разстояния.
Общото разстояние за първия посетен знак е разстоянието му от стартовия знак. Общото разстояние за всички останали знаци се получава като сума от разстоянието на този знак от предходния посетен знак и вече пресметнатото общо разстояние до предходния знак. 
За да улесни екипажите при разучаването на новите правила на състезанието, организационният комитет е отбелязал стартовия знак с номер 0 (нула), а всички знаци, които са разположени отдясно на стартовия, е отбелязал с положителни числа, съответстващи на техните разстояния до стартовия знак. Аналогично, знаците, разположение отляво на стартовия знак, са отбелязани с отрицателни числа, съответстващи на техните разстояния до стартовия знак. По този начин, ако знаците са поставени на позиции {-3,1,5}, сумата от общите разстояния при ред на посещаване {-3,1,5} е 3+(4+3)+(4+7) = 21. 
Напишете програма, която: 
а) чете от входния файл последователност от знаци, съответстващи на техните разстояния;
б) пресмята минималната сума от общите разстояния за определен от вас ред на посещаване;
в) извежда резултата в изходния файл.

-9

-6

-5

-2

1

3

4

10

Например, ако редът на посещаване за представения на горната фигура случай е  {1, 3, 4, 10, -2, -5, -6, -9} сумата от общите разстояния е 1+3+4+10+ 22+25+26+29=120. Най-добър е редът {1, 3, 4, -2, -5, -6, -9, 10} със сума на общите разстояния 1+3+4+10+13+14+17+36=98.

Вход
Входните данни се четат от файл “sailrace.in”. 
Първият ред съдържа цяло число L (1≤L≤200), съответстващо на броя на знаците, които всяка лодка трябва да посети (стартовият знак не е включен в този брой). Вторият ред съдържа последователността от знаци, подредени в нарастващ ред, като стартовият знак не е включен в нея.

Изход
Програмата трябва да изведе във файла “sailrace.out” единствен ред, съдържащ едно цяло число, съответстващо на намерената минимална сума от общи разстояния получени при избран ред на посещаване на знаците (оптимален ред на посещаване). Възможно е да има повече от един оптимален ред на посещаване, всеки от тях е приемлив.

Пример
sailrace.in
8
-9 -6 -5 -2 1 3 4 10	sailrace.out
98	

Формат: Във всеки от файловете числата в един ред са разделени с единичен интервал. Всички редове завършват с край на ред.

Време за изпълнение: 4 секунди.