계단 수열 만들기

원래 수열에서 이웃한 두 원소 $A_i, A_{i+1}$을 생각하자. 두 원소의 순서는 바꿀 수 없으므로, 두 원소 사이만 독립적으로 해결하면 된다.

$d=|A_i-A_{i+1}|$라고 하자.

$d=1$이면 이미 조건을 만족하므로 삽입이 필요 없다.

$d\ge 2$이면 두 원소 사이에 $d-1$개의 수를 삽입하면 된다. 예를 들어 $2$와 $6$ 사이에는 $3,4,5$를 넣으면 되므로 번의 연산이 필요하다.

$d=0$이면 두 원소가 같다. 이 경우 같은 두 수 사이에 그 수보다 $1$ 크거나 작은 수 하나를 넣으면 된다. 예를 들어 $5,5$ 사이에 $4$를 넣으면 $5,4,5$가 되고, 모든 이웃한 차이의 절댓값이 이 된다. 따라서 이 경우 필요한 연산 횟수는 이다.

따라서 각 $i$에 대해 다음 값을 더하면 된다.

$$\begin{cases} 1 & (|A_i-A_{i+1}|=0)\\ |A_i-A_{i+1}|-1 & (|A_i-A_{i+1}|\ge 1) \end{cases}$$

정답은 최대 약 $2 \times 10^{14}$까지 커질 수 있으므로 64비트 정수를 사용해야 한다. 시간 복잡도는 $O(N)$이다.