JackRabbit Slim

우리는 모두 토끼를 좋아한다, 그렇지? 안타깝게도 토끼는 우리를 좋아하지 않는다. 오히려 토끼가 좋아하는 것은 당근이다!

토끼는 당근을 너무 좋아해서 당근에 닿기 위해서라면 무엇이든 한다. 심지어 달리기도 한다. 쉽게 들릴지 모르지만 토끼는 게으르고, 활동적인 쪽은 jackrabbit이다. 그래서 이 문제는 토끼가 아니라 jackrabbit에 관한 문제다. 사실 이 문제는 Slim이라는 아주 특정한 검은꼬리 jackrabbit에 관한 문제다.

오늘 아침, 대회가 시작되기 전에 당근을 가득 실은 트럭이 Slim의 집 앞 도로를 지나갔다. 운 좋게도 도로 위에 당근 n개가 떨어졌다. 왼쪽에서 오른쪽으로 1부터 n까지 번호를 붙이자. 집을 나선 Slim은 당근 하나를 발견했다. 주변을 둘러본 뒤, 그날의 계획이 명확해졌다. 가장 가까운 당근을 찾아, 그곳으로 가서 먹고, 다시 반복하는 것이다.

Slim의 집 앞 도로는 길이 10^9인 직선 도로이고, 도로 위 i번째 당근은 좌표 x_i에 있다.

Slim이 j번째 당근의 위치에 서서 그것을 먹으며 하루를 시작한다고 하자. 그런 다음 당근이 남아 있는 한, 그는 다음 단계를 따른다.

• 남아 있는 당근 중 가장 가까운 것을 찾는다. 가장 가까운 당근이 두 개라면 오른쪽에 있는 것을 고른다.
• 그곳으로 달려가서 먹는다. 간단하다!

각 j에 대해, Slim이 j번째 당근을 먹으며 하루를 시작할 때 달리는 총 거리를 D_j라고 하자. 알 수 없는 이유로 우리는 모든 j(1 ≤ j ≤ n)에 대한 D_j 값의 합을 구하고 싶다.

입력의 첫 줄에는 당근의 개수 n(1 ≤ n ≤ 10^5)이 주어진다. 입력의 둘째 줄에는 n개의 공백으로 구분된 서로 다른 정수 x_1, ..., x_n(0 ≤ x_i ≤ 10^9)이 주어진다. 당근의 좌표는 증가하는 순서로 주어진다.

모든 D_j 값(j는 1부터 n까지)의 합을 정수로 출력한다.