Farmer John이 농장 울타리 구멍을 고치는 것을 잊어 $N$마리 소 $(1 \le N \le 1,000)$가 탈출해 난동을 부립니다! 소 한 마리가 울타리 밖에 있는 매분마다 1달러 피해를 냅니다. FJ는 각 소를 찾아가 굴레를 달아 진정시키고 피해를 멈춰야 합니다.

다행히 소들은 농장 밖 도로의 한 직선 위 서로 다른 위치에 있습니다. FJ는 출발하는 문(위치 0)을 기준으로 각 소 $i$의 위치 $P_i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$를 압니다.

FJ는 분당 한 거리 단위로 움직이고 굴레를 즉시 달 수 있습니다. 총 피해 비용을 최소화하는 방문 순서를 정하고, 그 최소 총 피해 비용을 계산하세요.

입력

• 줄 1: 소의 수 $N$입니다.
• 줄 $2\ldots N+1$: 줄 $i+1$에는 정수 $P_i$가 있습니다.

출력

• 줄 1: 최소 총 피해 비용입니다.

예제

입력 1

4
-2
-12
3
7

출력 1

50

참고

네 소는 위치 $-2$, $-12$, $3$, $7$에 있습니다.

최적 방문 순서는 $-2,3,7,-12$입니다. FJ는 2분 만에 $-2$에 도착하므로 그 소의 피해는 2달러입니다.

다음으로 위치 $3$까지 거리 5를 이동하며, 그 소의 누적 피해는 $2 + 5 = 7$달러입니다.

4분 더 걸려 $7$에 도착하면 그 소의 피해는 $7 + 4 = 11$달러입니다.

마지막으로 19분 걸려 $-12$에 도착하면 비용은 $11 + 19 = 30$달러입니다.

총 피해는 $2 + 7 + 11 + 30 = 50$달러입니다.

문제 출제: Chris Tzamos, 2006