가로수

직선 도로 한쪽에 가로수가 서로 다른 간격으로 심어져 있다. KOI 시는 새 가로수를 더 심어 모든 이웃한 가로수 사이의 간격을 같게 하려 한다. 예산을 아끼기 위해 새로 심는 가로수의 수는 가능한 한 적어야 한다.

가로수의 위치는 기준점에서 떨어진 거리로 나타내며, 모든 위치는 양의 정수이다.

가령 위치가 (1, 3, 7, 13)이라면 5, 9, 11에 가로수를 심으면 모든 간격이 2가 된다. 위치가 (2, 6, 12, 18)이라면 4, 8, 10, 14, 16에 심어야 모든 간격이 2가 된다.

이미 심어진 가로수의 위치가 주어질 때, 모든 이웃한 가로수 사이의 간격이 같아지도록 기존 가로수 사이에 새로 심어야 하는 가로수의 최소 개수를 구하라.

첫째 줄에 이미 심어진 가로수의 수 N이 주어진다. (3 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에 각 가로수의 위치가 한 줄에 하나씩 주어진다. 위치는 1 이상 1,000,000,000 이하의 서로 다른 정수이며, 기준점에서 가까운 순서로 주어진다.

첫째 줄에 모든 이웃한 가로수 사이의 간격이 같아지도록 새로 심어야 하는 가로수의 최소 개수를 출력한다.