피아노 조율

면접 대비

시간 제한2초메모리 제한1024 MB

요약

각 건반의 음높이 차이가 주어질 때, 인접한 건반끼리 정확히 한 단계씩 차이 나도록 조율하는 데 드는 최소 변화량의 합을 구합니다.

난이도: 쉬움10점 중 3점
유형: 정렬, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

잠시 후 콘서트가 시작되는데 피아노가 완전히 음이 맞지 않는다는 것을 알게 되었다. 상대 음감이 있어서 임의의 건반과 첫 번째 건반의 음높이 차이는 구별할 수 있다. 절대 음높이는 알 수 없지만, 건반끼리는 서로 맞출 수 있다. 각 건반의 음높이는 바로 앞 건반보다 정확히 1 높고, 바로 뒤 건반보다 정확히 1 낮아야 한다. 콘서트가 곧 시작되므로, 각 건반에 가하는 음높이 변화량의 절댓값을 모두 더한 전체 조율 노력을 최소화해야 한다. 예를 들어 그림 M.1은 입력 3에 대한 해 하나를 보여 주며, 이때 전체 조율 노력은 23이다.

그림 M.1: 입력 3의 시각화.

입력

첫 줄에 피아노 건반의 수 $n$ ( $2 \leq n \leq 10^5$ )이 주어진다. 둘째 줄에는 정수 $t_1,\dots,t_n$ ( $-2 \cdot 10^5 \leq t_i \leq 2 \cdot 10^5$ )이 주어지며, $t_i$ 는 $i$ 번째 건반과 첫 번째 건반의 음높이 차이를 나타낸다. $t_1$ 은 항상 $0$ 이다.

출력

전체 조율 노력의 최솟값을 출력한다.

예제5

예제 1
입력
```
7
0 1 2 3 4 5 6
```
예상 출력
```
0
```
예제 2
입력
```
5
0 1 4 3 6
```
예상 출력
```
4
```
예제 3
입력
```
6
0 -2 10 6 7 -1
```
예상 출력
```
23
```
예제 4
입력
```
4
0 -4 -2 1
```
예상 출력
```
7
```

예제 5

입력

9
0 23452 145043 -3423 -20 9845 435 -3 4453

예상 출력