Problema C - Entrega de Pizzas

A Pizzolim (Pizzas Olímpicas) tem uma loja instalada na maior avenida da cidade. Hoje é o dia de um grande acontecimento televisivo (vão ser transmitidas as Olimpíadas Nacionais de Informática, com uma câmara instalada no computador de cada participante) e todos querem ver! Por isso mesmo, um grande número de pedidos de pizza para entrega ao domicílio chegou quase à mesma hora. A Pizzolim apenas tem disponível um pizzaboy com uma pequena lambreta e tem de organizar a entrega das pizzas!

Podemos imaginar a avenida como sendo uma enorme linha recta com faixas de rodagem em ambos os sentidos. As posições de casas na estrada estão numeradas com números inteiros consecutivos. A loja da Pizzolim está situada na posição 0 e as casas que pediram uma entrega de pizzas estão colocadas à esquerda (coordenadas negativas) ou à direita (coordenadas positivas). A figura seguinte ilustra um exemplo com 5 casas colocadas nas posições -4, -1, 4, 5 e 6:

O objectivo é minimizar a soma dos tempos que cada casa espera pela pizza que pediu. Considera que todos os pedidos foram feitos ao mesmo tempo e que a lambreta consegue deslocar-se uma unidade de comprimento em cada unidade de tempo. Ao chegar a cada uma das casas que encomendou pizzas a entrega é "instantânea", e o pizzaboy pode deslocar-se imediatamente para a casa de uma outra entrega. Por exemplo, a lambreta podia visitar as casas na seguinte ordem:

-1 -> -4 -> 4 -> 5 -> 6

Neste caso, a lambreta chega em uma unidade de tempo à casa situada em -1. 3 unidades de tempo depois chega à posição -4. Aí inverte e dirige-se para a casa na posição 4, sendo que demora 8 unidades de tempo a lá chegar (para ir da posição -4 à 4). Daí demora 1 unidade de tempo a chegar à casa 5 e finalmente outra unidade de tempo para chegar à casa 6. Se escrevermos o tempo de espera de cada casa entre parênteses (tempo entre o início e a chegada da pizza a essa casa) temos a seguinte situação:

-1 (1) -> -4 (4) -> 4 (12) -> 5 (13) -> 6 (14) [total tempo espera: 44 = 1+4+12+13+14]

Seria possível fazer melhor? Uma alternativa seria por exemplo começar por ir para a direita de acordo com o seguinte percurso, que daria um tempo total de espera também igual a 44:

4 (4) -> 5 (5) -> 6 (6) -> -1 (13) -> -4 (16) [total tempo espera: 44 = 4+5+6+13+16]

No entanto, a melhor solução neste caso seria o seguinte percurso, em que o tempo de espera total é 40:

-1 (1) -> 4 (6) -> 5 (7) -> 6 (8) -> -4 (18) [total tempo espera: 40 = 1+6+7+8+18]

E para um caso geral, qual o percurso pelo qual as casas devem ser visitadas?

O Problema

Dado um conjunto de N casas dispostas numa linha e identificadas por coordenadas inteiras, a tua tarefa é calcular qual o percurso que minimiza a soma dos tempo de entrega, isto é, qual a ordem em que as casas devem ser visitadas de modo a que a soma do tempo que a lambreta demora a chegar a cada uma delas é a menor possível.

Input

Na primeira linha vem um número inteiro N, representando o número de casas.

Em cada uma uma das N linhas seguintes vem um número inteiro C_i indicando a posição da i-ésima casa. As casas vêm sempre por ordem estritamente crescente, nunca existindo duas casas na mesma posição.

Output

O output deve ser constituído por uma linha com um único inteiro indicando qual a menor soma de tempos de espera possível, tal como atrás descrito.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 60% dos pontos, acontece sempre que N ≤ 15.

Exemplo de Input 1

5
-4
-1
4
5
6

Exemplo de Output 1

40

Explicação do Input/Output 1

Corresponde à figura dada atrás no enunciado.

Exemplo de Input 2

3
-2
1
2

Exemplo de Output 2

9

Explicação do Input/Output 2

O melhor caminho é o seguinte:

1 (1) -> 2 (2) -> -2 (6) [total tempo espera: 9 = 1+2+6]