아기 토끼 timer 2s memory 512MB

KOI 마을에는 아기 토끼 한 마리가 살고 있다.

어느 날 당근을 운송하는 트럭 한 대가 도로 위에 N개의 당근을 떨어뜨렸다!

도로는 마을 입구로부터 시작된 직선 형태이고, 트럭은 입구에서 i번째로 가까운 당근을 입구에서 거리가 Ai 만큼 떨어진 곳에 떨어뜨렸다.

그 사실을 알게 된 토끼는 당근을 먹어치울 계획을 세웠다!

토끼는 다음과 같은 순서로 당근을 먹는다.

1. 한 당근이 있는 위치를 골라 그 자리에서 시작한다.

2. 토끼가 있는 위치의 당근을 먹는다.

3. 남아 있는 당근이 있다면 현재 위치로부터 가장 가까운 당근으로 뛰어간 다음, 2번으로 돌아간다.

(3번에서 가장 가까운 당근이 1개가 아니라면 오른쪽 당근으로 뛰어간다.)

토끼는 먹는 것은 좋아하지만 뛰는 것은 싫어한다.

그래서 토끼는 계획을 세우던 도중 N개의 각 당근을 시작점으로 할 때의 이동거리가 얼마인지 궁금해졌다.

여러분의 할 일은 1~N번 각각의 당근이 시작점일때 토끼가 뛰어가게될 거리의 전체 합을 구하는 것이다.