배고픈 개구리 빌리

개구리 빌리는 바위에 앉아 노을을 보고 있다가 배가 고파졌다. 주위를 둘러보니 발밑 시냇가에 작은 벌레들이 모여 있었다. 시냇물은 직선이고, 빌리가 앉아 있는 바위도 그 위에 있다. 빌리는 무척 배가 고파서 모든 벌레를 먹으려고 한다. 혀가 아주 길어서 바위에서 뛰어내리지 않고도 어떤 벌레든 먹을 수 있다. 단, 한 번에 한 마리씩만 먹을 수 있다.

멀리 혀를 내미는 것은 쉽지 않다. 빌리는 혀를 1cm 내밀 때마다 에너지 1을 쓴다. 빌리가 어떤 지점의 벌레를 먹을 때마다 그 왼쪽에 있던 벌레들과 오른쪽에 있던 벌레들은 놀라서 그 자리에서 시냇물을 따라 1cm씩 뛰어난다. 먹힌 벌레와 같은 지점에 있던 벌레들은 너무 충격을 받아 움직이지 않는다.

어떤 벌레가 빌리가 앉은 바위로 뛰어오르면, 빌리는 그 벌레를 곧바로 에너지 없이 먹는다. 이때 다른 벌레는 움직이지 않는다.

빌리는 모든 벌레를 먹는 데 필요한 최소 에너지가 몇인지 알고 싶다. 그 값을 구해 주자.

첫째 줄에 벌레의 수 $n$이 주어진다. ($1 \le n \le 100{\,}000$)

둘째 줄에 $n$개의 자연수가 주어진다. 각 수는 바위에서 해당 벌레까지의 거리이다. 모든 벌레는 바위의 한쪽 같은 직선 위에 있다. 거리는 오름차순으로 주어지며 $10^9$를 넘지 않는다.

빌리가 모든 벌레를 먹는 데 필요한 최소 에너지를 한 줄에 출력한다.

예제 설명. 먼저 빌리는 4 지점에 있는 벌레 한 마리를 먹는다. 같은 지점에 있던 다른 벌레는 움직이지 않고, 2 지점에 있던 벌레 두 마리는 1 지점으로 밀려난다. 4 지점에 남은 두 번째 벌레를 먹으면 1 지점에 있던 벌레 두 마리가 0 지점으로 뛰어오르고, 그 자리에서 곧바로 먹힌다.